Journal
INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, IPCO 2019
Volume 11480, Issue -, Pages 399-412Publisher
SPRINGER INTERNATIONAL PUBLISHING AG
DOI: 10.1007/978-3-030-17953-3_30
Keywords
Linear programming; Oracle complexity; Diophantine approximation; Exact solutions; Symbolic computation; Rational arithmetic; Extended-precision arithmetic; Iterative refinement
Categories
Funding
- Research Campus MODAL - German Ministry of Education and Research [05M14ZAM]
Ask authors/readers for more resources
Linear programming is a foundational tool for many aspects of integer and combinatorial optimization. This work studies the complexity of solving linear programs exactly over the rational numbers through use of an oracle capable of returning limited-precision LP solutions. Under mild assumptions, it is shown that a polynomial number of calls to such an oracle and a polynomial number of bit operations, is sufficient to compute an exact solution to an LP. Previous work has often considered oracles that provide solutions of an arbitrary specified precision. While this leads to polynomial-time algorithms, the level of precision required is often unrealistic for practical computation. In contrast, our work provides a foundation for understanding and analyzing the behavior of the methods that are currently most effective in practice for solving LPs exactly.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available