abstract
An {\em Abstract Optimization Problem} (AOP) is a triple
$(H,<, \Phi)$
where
$H$ is a finite set, $<$ a total order on $2^{H}$ and $\Phi$ an
oracle
that,
for given $F\subseteq G\subseteq H$, either reports that
$F=\min_{<}\{F'\mid F'\subseteq G\}$ or
returns a set $F'\subseteq G$ with $F'<F$. To solve the problem
means
to find 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 to 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.