A subexponential algorithm for abstract optimization problems

An Abstract Optimization Problem (AOP) is a triple (H, <, Φ) where H is a finite set, < a total order on 2 H and Φ an oracle that, for given F ⊆ G ⊆ H, either reports that F = min<{F ′ | F ′ ⊆ G} or returns a set F ′ ⊆ 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 √ n+O ( 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 nfacet) 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