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

DOI10.1016/0020-0190(86)90037-2zbMATH Open1418.90148OpenAlexW2009436609MaRDI QIDQ2003407FDOQ2003407

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

• 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
• Title not available (Why is that?)

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
• Two-variable linear programming in parallel
• On the ball spanned by balls
• 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)