Input: | An oracle for a function
s: {0,1} defining an
AOF-orientation of the graph of the ^{d} ¾® {+,-}^{d}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 e see Gärtner [24].
^{2sqrt(d)}-1In 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 |
---|