Polynomial algorithms for linear programming over the algebraic numbers

DOI10.1007/BF01188714zbMath0855.68039OpenAlexW2024997126MaRDI QIDQ1343466

Peter A. Beling, Ilan Adler

Publication date: 28 February 1995

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01188714

zbMATH Keywords

computational complexitylinear programmingpolynomial-time algorithmsalgebraic numbersellipsoid method

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Parallel algorithms in computer science (68W10)

Related Items (6)

On linear programming and matrix scaling over the algebraic numbers ⋮ On the realisability of double-cross matrices by polylines in the plane ⋮ The equivalence of linear programs and zero-sum games ⋮ Tractability conditions for numeric CSPs ⋮ Polynomial algorithms for LP over a subring of the algebraic integers with applications to LP with circulant matrices ⋮ On a transfer theorem for the \(\text{P}\neq \text{NP}\) conjecture

Cites Work

• Polynomial algorithms for LP over a subring of the algebraic integers with applications to LP with circulant matrices
• A new polynomial-time algorithm for linear programming
• Complexity of linear programming
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• Towards a Genuinely Polynomial Algorithm for Linear Programming
• Linear Programming in Linear Time When the Dimension Is Fixed
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Polynomial algorithms for linear programming over the algebraic numbers