Linear programming in \(O(n\times 3^{d^2})\) time

DOI10.1016/0020-0190(86)90037-2zbMath1418.90148OpenAlexW2009436609MaRDI QIDQ2003407

Kenneth L. Clarkson

Publication date: 8 July 2019

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(86)90037-2

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05)

Related Items

Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given points, Efficient piecewise-linear function approximation using the uniform metric, A combinatorial bound for linear programming and related problems, A polynomial algorithm for a continuous bilevel knapsack problem, Decomposable multi-parameter matroid optimization problems., Small-dimensional linear programming and convex hulls made easy, Weighted search in the plane, Two-variable linear programming in parallel, Algorithms for weak and wide separation of sets, Linear time algorithms for some separable quadratic programming problems, Cutting hyperplanes for divide-and-conquer, Two-variable linear programming in parallel, On the ball spanned by balls, Characterizing multiterminal flow networks and computing flows in networks of small treewidth

Cites Work

• Unnamed Item
• A new polynomial-time algorithm for linear programming
• Linear Programming in Linear Time When the Dimension Is Fixed
• On a Multidimensional Search Technique and Its Application to the Euclidean One-Centre Problem