Polynomial algorithms for a class of linear programs

DOI10.1007/BF01584235zbMath0509.90056MaRDI QIDQ4749597

No author found.

Publication date: 1981

Published in: Mathematical Programming (Search for Journal in Brave)

zbMATH Keywords

projection schemeapproximate solutionpolynomial algorithmtotally unimodular matrixtotal unimodularityscaling schemesix algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Integer programming (90C10) Linear programming (90C05) Matrices of integers (15B36)

Related Items (10)

A decomposition property of polyhedra ⋮ Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration ⋮ Scaling: A general framework ⋮ Proximal level bundle methods for convex nondifferentiable optimization, saddle-point problems and variational inequalities ⋮ On Chubanov's Method for Linear Programming ⋮ A Sampling Kaczmarz--Motzkin Algorithm for Linear Feasibility ⋮ An appraisal of computational complexity for operations researchers ⋮ An exact and polynomial approach for a bi-objective integer programming problem regarding network flow routing ⋮ Projection algorithms for linear programming ⋮ A comprehensive simplex-like algorithm for network optimization and perturbation analysis

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Decomposition of regular matroids
• Normal hypergraphs and the perfect graph conjecture
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Paths, Trees, and Flowers
• Integral Extreme Points
• Systems of distinct representatives and linear algebra
• Convergence rate of the gradient descent method with dilatation of the space
• The Relaxation Method for Linear Inequalities
• The Relaxation Method for Linear Inequalities

This page was built for publication: Polynomial algorithms for a class of linear programs