A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
Daniel Dadush, Sophie Huiberts, Bento Natura, László A. Végh
Abstract
Following the breakthrough work of Tardos (Oper. Res. ’86) in the bit-complexity model, Vavasis and Ye (Math. Prog. ’96) gave the first exact algorithm for linear programming in the real model of computation with running time depending only on the constraint matrix. For solving a linear program (LP) max c x, Ax = b, x ≥ 0, A ∈ m × n , Vavasis and Ye developed a primal-dual interior point method using a ‘layered least squares’ (LLS) step, and showed that O(n 3.5 log(χ A +n)) iterations suffice to solve (LP) exactly, where χ A is a condition measure controlling the size of solutions to linear systems related to A.
Topics & Concepts
Linear programmingInterior point methodMathematicsMatrix (chemical analysis)AlgorithmComputationTime complexityScalingConstraint (computer-aided design)Running timeLinear systemInvariant (physics)LTI system theoryDiscrete mathematicsCombinatoricsMathematical analysisMathematical physicsComposite materialMaterials scienceGeometryAdvanced Optimization Algorithms ResearchComplexity and Algorithms in GraphsAdvanced Graph Theory Research