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

68Q25: Analysis of algorithms and problem complexity

65K05: Numerical mathematical programming methods

90C05: Linear programming

Related Items

A PARALLEL ALGORITHM FOR FIXED-DIMENSIONAL LINEAR PROGRAMMING∗, A randomized scheme for speeding up algorithms for linear and convex programming problems with high constraints-to-variables ratio, 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 subexponential bound for linear programming, Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given points

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