Combinatorial linear programming: Geometry can help
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Extreme-point and pivoting methods (90C49) Abstract computational complexity for mathematical programming problems (90C60)
The purpose of this work is to contribute to the study of linear programming complexity, in particular to its combinatorial complexity in the RAM model. It is well known that it would be useful to be able to derive pivot rules that make the simplex method polynomial in terms of the number of pivot rules. Following this line the author considers a class of problems (defined by Matoušek) and describes a simplex algorithm with Kalai's pivot rule called random facet adapted to this class of problems. This algorithm is proved to be polynomial on linear problems of this class. Upper and lower bounds are obtained. For the entire collection see [Zbl 0898.00029].
- Combinatorial optimization in geometry
- scientific article; zbMATH DE number 3860890
- A geometrical approach to the linear complementarity problem
- scientific article; zbMATH DE number 1444288
- Geometric algorithms and combinatorial optimization
- scientific article; zbMATH DE number 4174695
- Linear Programming Approach to Solve Geometric Programming Problem
- scientific article; zbMATH DE number 4176845
This page was built for publication: Combinatorial linear programming: Geometry can help
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4247198)
