scientific article; zbMATH DE number 1182931

MaRDI QIDQ4401028zbMATH OpenFDO

Authors Martin Dyer, Nimrod Megiddo

Publication date 19 January 1999

zbMATH Keywords

computational geometryfixed-dimensional linear programminglinear time algorithmsparallel algorithms

Mathematics Subject Classification ID

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

Review text

Linear programming has many important practical applications, and has also given rise to a wide body of theory. Here, we consider the linear programming problem in the form of maximizing a linear function of \(d\) variables subject to \(n\) linear inequalities. We focus on the relationship of the problem to computational geometry, i.e., we consider the problem in small dimension. More precisely, we concentrate on the case where \(d\ll n\), i.e., \(d= d(n)\) is a function that grows very slowly with \(n\). By linear programming duality, this also includes the case \(n\ll d\). This has been called fixed-dimensional linear programming, though our viewpoint here will not treat \(d\) as constant. In this case, there are strongly polynomial algorithms, provided the rate of growth of \(d\) with \(n\) is small enough. The plan of the chapter is as follows. First we consider the simplex method, we review deterministic linear time algorithms and randomized algorithms, and we consider the derandomization of the latter. We examine parallel algorithms for this problem, and finally we briefly discuss related issues. The emphasis throughout is on complexity-theoretic bounds for the linear programming problem. For the entire collection see [Zbl 0890.52001].

Recommendations

• Las Vegas algorithms for linear and integer programming when the dimension is small
• A Deterministic ${\operatorname{Poly}}(\log \log N)$-TimeN-Processor Algorithm for Linear Programming in Fixed Dimension
• A randomized algorithm for fixed-dimensional linear programming

Cited in

(11)

• Small-dimensional linear programming and convex hulls made easy
• A randomized algorithm for fixed-dimensional linear programming
• Walking around fat obstacles.
• Efficient algorithms for the minimum diameter bridge problem
• Randomized combinatorial algorithms for linear programming when the dimension is moderately high
• On the space complexity of linear programming with preprocessing
• scientific article; zbMATH DE number 437553 (Why is no real title available?)
• Linear Time Algorithms for Two- and Three-Variable Linear Programs
• Linear Programming in Linear Time When the Dimension Is Fixed
• Low-Dimensional Linear Programming with Violations
• Data mapping of linear programming on fixed-size hypercubes

This page was built for publication:

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