A randomized algorithm for fixed-dimensional linear programming

DOI10.1007/BF01587088zbMath0681.90054WikidataQ56324135 ScholiaQ56324135MaRDI QIDQ1823854

Martin Dyer, Alan M. Frieze

Publication date: 1989

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Linear programming (90C05)

Related Items

Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given points, A PARALLEL ALGORITHM FOR FIXED-DIMENSIONAL LINEAR PROGRAMMING∗, A subexponential bound for linear programming, A combinatorial bound for linear programming and related problems, Random sampling with removal, Convex hulls of samples from spherically symmetric distributions, Euclidean minimum spanning trees and bichromatic closest pairs, Small-dimensional linear programming and convex hulls made easy, Dynamic point location in arrangements of hyperplanes, A randomized scheme for speeding up algorithms for linear and convex programming problems with high constraints-to-variables ratio, Empirical orthogonal constraint generation for multidimensional 0/1 knapsack problems, A characterization theorem and an algorithm for a convex hull problem

Cites Work

• Unnamed Item
• \(\epsilon\)-nets and simplex range queries
• New applications of random sampling in computational geometry
• Linear Time Algorithms for Two- and Three-Variable Linear Programs
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• Linear Programming in Linear Time When the Dimension Is Fixed
• On a Multidimensional Search Technique and Its Application to the Euclidean One-Centre Problem
• Probability Inequalities for Sums of Bounded Random Variables