Go backward to 28 AOF Cube Programming
Go up to 5 Optimization

29 USO Cube Programming

Input: An oracle for a function s: {0,1}d ¾® {+,-}d defining a US-orientation of the graph of the d-cube
Output: The sink of the orientation
Status (general): Open
Status (fixed dim.): Constant time
Szabó and Welzl [63] describe a randomized algorithm solving the problem in an expected number of O(ad) oracle calls with a=sqrt(43/20)<1.467 and a deterministic algorithm that needs O(1.61d) oracle calls. Plugging an optimal algorithm for the three-dimensional case (found by Günter Rote) into their algorithm, Szabó and Welzl even obtain an O(1.438d) randomized algorithm.

The problem not only generalizes Problem 28, but also certain linear complementary problems and smallest enclosing ball problems.

In fixed dimension the problem is trivial by mere enumeration.