On Chubanov's Method for Linear Programming
From MaRDI portal
Abstract: We discuss the method recently proposed by S. Chubanov for the linear feasibility problem. We present new, concise proofs and interpretations of some of his results. We then show how our proofs can be used to find strongly polynomial time algorithms for special classes of linear feasibility problems. Under certain conditions, these results provide new proofs of classical results obtained by Tardos, and Vavasis and Ye.
Recommendations
- On Chubanov's method for solving a homogeneous inequality system
- On the convex programming approach to linear programming
- scientific article; zbMATH DE number 3978821
- scientific article; zbMATH DE number 16591
- scientific article; zbMATH DE number 3943551
- scientific article; zbMATH DE number 883355
- scientific article; zbMATH DE number 2047294
- scientific article; zbMATH DE number 4062817
- scientific article; zbMATH DE number 778138
- Implementing cholesky factorization for interior point methods of linear programming
Cites work
- A primal-dual interior point method whose running time depends only on the constraint matrix
- A randomized Kaczmarz algorithm with exponential convergence
- A strongly polynomial algorithm for linear systems having a binary solution
- A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
- An efficient rescaled perceptron algorithm for conic systems
- Boundedness Theorems for the Relaxation Method
- Computational Experience in Solving Linear Programs
- scientific article; zbMATH DE number 1219584 (Why is no real title available?)
- On relaxation methods for systems of linear inequalities
- On the non-polynomiality of the relaxation method for systems of linear inequalities
- Polynomial algorithms for a class of linear programs
- Randomized Kaczmarz solver for noisy linear systems
- Relaxation, new combinatorial and polynomial algorithms for the linear feasibility problem
- The Relaxation Method for Linear Inequalities
- The Relaxation Method for Linear Inequalities
- The Relaxation Method for Solving Systems of Linear Inequalities
Cited in
(18)- A polynomial projection-type algorithm for linear programming
- Solving conic systems via projection and rescaling
- A comparative note on the relaxation algorithms for the linear semi-infinite feasibility problem
- An extension of Chubanov's algorithm to symmetric cones
- Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration
- scientific article; zbMATH DE number 5898062 (Why is no real title available?)
- Rescaled coordinate descent methods for linear programming
- On Chubanov's method for solving a homogeneous inequality system
- An extension of Chubanov's polynomial-time linear programming algorithm to second-order cone programming
- An improved version of Chubanov's method for solving a homogeneous feasibility problem
- A strongly polynomial-time algorithm for the strict homogeneous linear-inequality feasibility problem
- Using Nemirovski's Mirror-Prox method as basic procedure in Chubanov's method for solving homogeneous feasibility problems
- A Computational Framework for Solving Nonlinear Binary Optimization Problems in Robust Causal Inference
- Rescaling algorithms for linear conic feasibility
- A sampling Kaczmarz-Motzkin algorithm for linear feasibility
- A new extension of Chubanov's method to symmetric cones
- A symmetry-based explanation of the main idea behind Chubanov's linear programming algorithm
- Relaxation, new combinatorial and polynomial algorithms for the linear feasibility problem
This page was built for publication: On Chubanov's Method for Linear Programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2962562)
