A strongly polynomial algorithm for linear systems having a binary solution

DOI10.1007/S10107-011-0445-3MaRDI QIDQ715067zbMATH OpenOpenAlexFDO

Authors Sergei Chubanov

Publication date 15 October 2012

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10107-011-0445-3

zbMATH Keywords

integer solutionslinear programmingpolynomial algorithm

Mathematics Subject Classification ID

Linear programming (90C05) Boolean programming (90C09)

Review text

The paper describes a strongly polynomial algorithm which either finds a solution to a linear system with integer coefficients, or correctly decides that the system does not have 0,1-solutions. The algorithm can be used as a basis for the construction of a polynomial algorithm for linear programming, which differs substantially from the well-known polynomial algorithms. The most important properties on which the method is based are the (Hahn-Banach) separation theorem for disjoint convex sets and the Cauchy-Schwarz inequality.

Recommendations

• A strongly polynomial algorithm for a new class of linear inequalities¹
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• scientific article; zbMATH DE number 1161055
• Towards a Genuinely Polynomial Algorithm for Linear Programming
• A Strongly Polynomial Algorithm for a Special Class of Linear Programs

Cites work

• A new polynomial-time algorithm for linear programming
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• scientific article; zbMATH DE number 3644821 (Why is no real title available?)
• Systems of distinct representatives and linear algebra
• The many facets of linear programming
• The Relaxation Method for Linear Inequalities
• The Relaxation Method for Linear Inequalities

Cited in

(37)

• A polynomial projection-type algorithm for linear programming
• Solving conic systems via projection and rescaling
• An extension of Chubanov's algorithm to symmetric cones
• A note on submodular function minimization by Chubanov's LP algorithm
• Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration
• A simple method for convex optimization in the oracle model
• A polynomial-time descent method for separable convex optimization problems with linear constraints
• An algorithm for binary linear programming
• On Chubanov's Method for Linear Programming
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• Strongly polynomial algorithm for solving the general problem of least modules
• Rescaled coordinate descent methods for linear programming
• On Chubanov's method for solving a homogeneous inequality system
• scientific article; zbMATH DE number 3923955 (Why is no real title available?)
• Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• A Strongly Polynomial Algorithm for a Special Class of Linear Programs
• scientific article; zbMATH DE number 1161055 (Why is no real title available?)
• An extension of Chubanov's polynomial-time linear programming algorithm to second-order cone programming
• A strongly polynomial algorithm for a new class of linear inequalities¹
• A strongly polynomial-time algorithm for the strict homogeneous linear-inequality feasibility problem
• A strongly polynomial algorithm for bimodular integer linear programming
• Binary solutions to large systems of linear equations
• A Computational Framework for Solving Nonlinear Binary Optimization Problems in Robust Causal Inference
• Rescaling algorithms for linear conic feasibility
• Complete Algorithms for Algebraic Strongest Postconditions and Weakest Preconditions in Polynomial ODE’S
• A sampling Kaczmarz-Motzkin algorithm for linear feasibility
• A Non-2-step Nilsystem With Linear Polynomial Complexity
• Computational performance of a projection and rescaling algorithm
• Projection and Rescaling Algorithm for Finding Maximum Support Solutions to Polyhedral Conic Systems
• A deterministic rescaled perceptron algorithm
• Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• An efficient linearization technique for mixed 0-1 polynomial problem
• A new extension of Chubanov's method to symmetric cones
• A symmetry-based explanation of the main idea behind Chubanov's linear programming algorithm
• Minimizing convex functions with rational minimizers
• A simple method for convex optimization in the oracle model
• A polynomial projection algorithm for linear feasibility problems

This page was built for publication: A strongly polynomial algorithm for linear systems having a binary solution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q715067)