The complexity of linear programming
From MaRDI portal
Publication:5904560
DOI10.1016/0304-3975(80)90031-6zbMath0446.90049OpenAlexW1967036113MaRDI QIDQ5904560
David P. Dobkin, Steven P. Reiss
Publication date: 1980
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(80)90031-6
Related Items
Computing circular separability, Filling polyhedral molds, Nonlinear mixing dynamical systems, On the complexity of d-dimensional Voronoi diagrams, Foundations of operations research: from linear programming to data envelopment analysis, Learning in parallel, Rational search, Linear programming is log-space hard for P, Approximating linear programming is log-space complete for P, Men and progress in linear programming, Algorithms and complexity analysis for some flow problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Some simplified NP-complete graph problems
- Complete problems for deterministic polynomial time
- The densest hemisphere problem
- A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem
- Linear programming is log-space hard for P
- Efficient search for rationals
- Finding the intersection of n half-spaces in time O(n log n)
- Heights of convex polytopes
- A class of linear programming problems requiring a large number of iterations
- An efficient algorithm for determining the convex hull of a finite planar set
- On the identification of the convex hull of a finite set of points in the plane
- Linear Inequalities and Related Systems. (AM-38)
- An Algorithm for Finding All Vertices of Convex Polyhedral Sets
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- On the Structure of Polynomial Time Reducibility
- Multidimensional Searching Problems
- Convex hulls of finite sets of points in two and three dimensions
- A bad network problem for the simplex method and other minimum cost flow algorithms
- On The Number of Faces of a Convex Polytope
- On the Number of Vertices of a Convex Polytope
- Algorithms for frames and lineality spaces of cones
- An Algorithm for Convex Polytopes
- Polytopes, graphs, and complexes
- Generating All the Faces of a Polyhedron
- An Algorithm for Determining Irrelevant Constraints and all Vertices in Systems of Linear Inequalities
- An Algorithm for the Extreme Rays of a Pointed Convex Polyhedral Cone
