A Subexponential Algorithm for Abstract Optimization Problems
Bernd Gärtner · SIAM Journal on Computing · 1995
An abstract optimization problem (AOP) is a triple $(H, <, \Phi)$ where H is a finite set, $< $ is a total order on $2^{H}$, and $\Phi $ is an oracle that, for given $F \subseteq G \subseteq H$, either reports that $F = \min_{<} \{ F' | F' \subseteq G\}$ or returns a set $F' \subseteq G$ with $F' < F$. Solving the problem means finding the minimum set in H. We present a randomized algorithm that solves any AOP with an expected number of at most \[ e^{2\sqrt n + O(\sqrt[4]{n}\ln n)} \] oracle calls, $n = |H|$. In contrast, any deterministic algorithm needs to make $2^{n} - 1$ oracle calls in the worst case. The algorithm is applied to the problem of finding the distance between two n-vertex (or n-facet) convex polyhedra in d-space, and the computation of the smallest ball containing n points in d-space; for both problems we give the first subexponential bounds in the arithmetic model of computation.