Linear programming using limited-precision oracles
DOI10.1007/s10107-019-01444-6zbMath1450.90006arXiv1912.12820OpenAlexW3011671470WikidataQ126783486 ScholiaQ126783486MaRDI QIDQ5918922
Ambros M. Gleixner, Daniel E. Steffy
Publication date: 28 August 2020
Published in: Mathematical Programming. Series A. Series B, Integer Programming and Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1912.12820
linear programmingsymbolic computationDiophantine approximationexact solutionsiterative refinementrational arithmeticoracle complexityextended-precision arithmetic
Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Interval and finite arithmetic (65G30) Diophantine approximation in probabilistic number theory (11K60)
Related Items
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A new polynomial-time algorithm for linear programming
- A polynomial-time algorithm, based on Newton's method, for linear programming
- Factoring polynomials with rational coefficients
- Geometric algorithms and combinatorial optimization
- The final NETLIB-LP results
- Exact arithmetic at low cost. -- A case study in linear programming
- Exact solutions to linear programming problems
- Solving linear programs with finite precision. II: Algorithms
- How Tight is Hadamard's Bound?
- Roundoff-Error-Free Algorithms for Solving Linear Systems via Cholesky and LU Factorizations
- Iterative Refinement for Linear Programming
- Solving Very Sparse Rational Systems of Equations
- An LLL Algorithm with Quadratic Complexity
- Polynomial algorithms in linear programming
- Note sur les $Q$-matrices d’Edmonds
- Acceleration of Euclidean Algorithm and Rational Number Reconstruction
- Exact solutions to linear systems of equations using output sensitive lifting
- A BLAS based C library for exact linear algebra on integer matrices
- Roundoff-Error-Free Basis Updates of LU Factorizations for the Efficient Validation of Optimality Certificates
- Systems of distinct representatives and linear algebra