Go backward to 27 Vertex With Specified Objective ValueGo up to 5 OptimizationGo forward to 29 USO Cube Programming |
XHTML 1.0 |

Input: | An oracle for a function
σ: {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 |
---|

Why are some symbols not displayed correctly? |