Go backward to 27 Vertex With Specified Objective Value
Go up to 5 Optimization
Go forward to 29 USO Cube Programming

28 AOF Cube Programming

Input: An oracle for a function s: {0,1}d ¾® {+,-}d defining an AOF-orientation of the graph of the d-cube
Output: The sink of the orientation
Status (general): Open
Status (fixed dim.): Constant time
The problem can be solved in a subexponential number of oracle calls by the random facet variant of the simplex algorithm due to Kalai [36]. For a derivation of the explicit bound e2sqrt(d)-1 see Gärtner [24].

In fixed dimension the problem is trivial by mere enumeration.

The problem generalizes linear programming problems whose sets of feasible solutions are combinatorially equivalent to cubes.