A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
From MaRDI portal
Publication:6120839
DOI10.1007/s10107-023-01956-2OpenAlexW2996305132MaRDI QIDQ6120839
Sophie Huiberts, Bento Natura, László A. Végh, Daniel Dadush
Publication date: 21 February 2024
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-023-01956-2
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Information geometry and interior-point algorithms in semidefinite programs and symmetric cone programs
- Curvature integrals and iteration complexities in SDP and symmetric cone programs
- On bounds for scaled projections and pseudoinverses
- A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms
- A strongly polynomial minimum cost circulation algorithm
- A polynomial-time algorithm, based on Newton's method, for linear programming
- On scaled projections and pseudoinverses
- On the complexity of following the central path of linear programs by linear extrapolation. II
- A modified layered-step interior-point algorithm for linear programming
- It is possible to know a problem instance is ill-posed? Some foundations for a general theory of condition numbers
- A primal-dual interior point method whose running time depends only on the constraint matrix
- A note on properties of condition numbers
- Mathematical problems for the next century
- Approximating the complexity measure of Vavasis-Ye algorithm is NP-hard
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- A bound for the number of different basic solutions generated by the simplex method
- On circuit diameter bounds via circuit imbalances
- Improved complexity results on solving real-number linear feasibility problems
- A Simple Variant of the Mizuno--Todd--Ye Predictor-Corrector Algorithm and Its Objective-Function-Free Complexity
- The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate
- A Strongly Polynomial Algorithm for Generalized Flow Maximization
- A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
- Towards a Genuinely Polynomial Algorithm for Linear Programming
- On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
- A Polynomial Predictor-Corrector Trust-Region Algorithm for Linear Programming
- The Relaxation Method for Solving Systems of Linear Inequalities
- On the Implementation of a Primal-Dual Interior Point Method
- Path-Following Methods for Linear Programming
- On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
- Stable Numerical Algorithms for Equilibrium Systems
- A Variant of the Vavasis--Ye Layered-Step Interior-Point Algorithm for Linear Programming
- Log-Barrier Interior Point Methods Are Not Strongly Polynomial
- Incorporating Condition Measures into the Complexity Theory of Linear Programming
- A Simpler and Faster Strongly Polynomial Algorithm for Generalized Flow Maximization
- A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
- Solving tall dense linear programs in nearly linear time
- A Deterministic Linear Program Solver in Current Matrix Multiplication Time
- A Dantzig-Wolfe-Like Variant of Karmarkar's Interior-Point Linear Programming Algorithm
- Solving linear programs in the current matrix multiplication time
- A New Iteration-Complexity Bound for the MTY Predictor-Corrector Algorithm
- Multiplying matrices faster than coppersmith-winograd
- A New Complexity Result on Solving the Markov Decision Problem
- Pivot Rules for Circuit-Augmentation Algorithms in Linear Optimization
- Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems
This page was built for publication: A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
