Linear programming in O(n 3d^2) time

DOI10.1016/0020-0190(86)90037-2MaRDI QIDQ2003407zbMATH OpenOpenAlexFDO

Authors 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

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

Cites work

• scientific article; zbMATH DE number 3644821 (Why is no real title available?)
• 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

Cited in

(14)

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

This page was built for publication: Linear programming in \(O(n\times 3^{d^2})\) time

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