backup forward

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 σ: {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.

backup forward Why are some symbols not displayed correctly?