ISSN:
1432-0541
Keywords:
Computational geometry
;
Combinatorial optimization
;
Linear programming
;
Smallest enclosing ball
;
Smallest enclosing ellipsoid
;
Randomized incremental algorithms
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We present a simple randomized algorithm which solves linear programs withn constraints andd variables in expected $$\min \{ O(d^2 2^d n),e^{2\sqrt {dIn({n \mathord{\left/ {\vphantom {n {\sqrt d }}} \right. \kern-\nulldelimiterspace} {\sqrt d }})} + O(\sqrt d + Inn)} \}$$ time in the unit cost model (where we count the number of arithmetic operations on the numbers in the input); to be precise, the algorithm computes the lexicographically smallest nonnegative point satisfyingn given linear inequalities ind variables. The expectation is over the internal randomizations performed by the algorithm, and holds for any input. In conjunction with Clarkson's linear programming algorithm, this gives an expected bound of $$O(d^2 n + e^{O(\sqrt {dInd} )} ).$$ The algorithm is presented in an abstract framework, which facilitates its application to several other related problems like computing the smallest enclosing ball (smallest volume enclosing ellipsoid) ofn points ind-space, computing the distance of twon-vertex (orn-facet) polytopes ind-space, and others. The subexponential running time can also be established for some of these problems (this relies on some recent results due to Gärtner).
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01940877
Permalink
