Linear programming — Randomization and abstract frameworks

DOI10.1007/3-540-60922-9_54MaRDI QIDQ4593969zbMATH OpenOpenAlexFDO

Authors B. Gärtner, Emo Welzl

Publication date 16 November 2017

Published in STACS 96 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60922-9_54

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Linear programming (90C05) Nonlinear programming (90C30) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• A randomized algorithm for fixed-dimensional linear programming
• Random projections for linear programming
• A randomized polynomial-time simplex algorithm for linear programming
• scientific article; zbMATH DE number 4074817
• On linear programs with random costs
• scientific article; zbMATH DE number 1003270
• scientific article; zbMATH DE number 176291
• Random linear programs with many variables and few constraints
• Randomized combinatorial algorithms for linear programming when the dimension is moderately high
• scientific article; zbMATH DE number 1487878

Cited in

(21)

• Some randomized algorithms for convex quadratic programming
• Learning fixed-dimension linear thresholds from fragmented data
• A subexponential bound for linear programming
• A distributed simplex algorithm for degenerate linear programs and multi-agent assignments
• The 2-center problem in three dimensions
• Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location
• Random sampling with removal
• Random edge can be exponential on abstract cubes
• A randomized polynomial-time simplex algorithm for linear programming
• Exact primitives for smallest enclosing ellipses
• A randomized center path method for a class of linear programming problems
• scientific article; zbMATH DE number 1003270 (Why is no real title available?)
• Random linear programs with many variables and few constraints
• scientific article; zbMATH DE number 1487878 (Why is no real title available?)
• scientific article; zbMATH DE number 1775049 (Why is no real title available?)
• Helly-type theorems for approximate covering
• Clarkson's algorithm for violator spaces
• Property testing of LP-type problems
• A randomized scheme for speeding up algorithms for linear and convex programming problems with high constraints-to-variables ratio
• Unique sink orientations of grids
• Violator spaces: Structure and algorithms

This page was built for publication: Linear programming — Randomization and abstract frameworks

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