On Chubanov's Method for Linear Programming

DOI10.1287/ijoc.2013.0569zbMath1356.90081arXiv1204.2031OpenAlexW2146263335MaRDI QIDQ2962562

Jesús A. De Loera, Amitabh Basu, Mark Junod

Publication date: 17 February 2017

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1204.2031

zbMATH Keywords

linear programmingrelaxation methodsstrongly polynomial time algorithms

Mathematics Subject Classification ID

Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05)

Related Items (10)

A Computational Framework for Solving Nonlinear Binary Optimization Problems in Robust Causal Inference ⋮ Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration ⋮ Rescaled Coordinate Descent Methods for Linear Programming ⋮ 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 ⋮ Rescaling Algorithms for Linear Conic Feasibility ⋮ A Sampling Kaczmarz--Motzkin Algorithm for Linear Feasibility ⋮ A strongly polynomial-time algorithm for the strict homogeneous linear-inequality feasibility problem ⋮ An extension of Chubanov's polynomial-time linear programming algorithm to second-order cone programming

Uses Software

• MIPLIB

Cites Work

• Unnamed Item
• Relaxation, new combinatorial and polynomial algorithms for the linear feasibility problem
• A strongly polynomial algorithm for linear systems having a binary solution
• Randomized Kaczmarz solver for noisy linear systems
• A randomized Kaczmarz algorithm with exponential convergence
• On relaxation methods for systems of linear inequalities
• A primal-dual interior point method whose running time depends only on the constraint matrix
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• An Efficient Rescaled Perceptron Algorithm for Conic Systems
• The Relaxation Method for Solving 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
• Boundedness Theorems for the Relaxation Method
• Computational Experience in Solving Linear Programs
• The Relaxation Method for Linear Inequalities
• The Relaxation Method for Linear Inequalities

This page was built for publication: On Chubanov's Method for Linear Programming