| 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. |
| Related problems: | 25, 29 |
|---|