A subexponential algorithm for abstract optimization problems

Publisher Website
Google Scholar
Abstract
An abstract optimization problem (AOP) is a triple (H,<, phi ) where H is a finite set, < a linear order on 2/sup H/ and phi an oracle that, for given F contained in G contained in H, determines whether F=min(2/sup G/), and if not, returns a smaller set. To solve the problem means to find min(2/sup H/). The author presents a randomized algorithm that solves any AOP with an expected number of O(e/sup O( square root mod H mod )/) oracle calls. In contrast, any deterministic algorithm needs to make 2/sup mod H mod /-1 oracle calls in the worst case. The algorithm is applied to the problem of finding the minimum distance of two polyhedra in d-space, which gives the first subexponential bound in d for this problem. Another application is the computation of the smallest ball containing n points in d-space; the previous bounds for this problem were also exponential in d.

This publication has 10 references indexed in Scilit: