Go backward to 27 Vertex With Specified Objective Value
Go up to 5 Optimization
Go forward to 29 USO Cube Programming
|
Go backward to 27 Vertex With Specified Objective Value Go up to 5 Optimization Go forward to 29 USO Cube Programming |
XHTML 1.0 |
| 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. |
| Related problems: | 25, 29 |
|---|
|
|
Why are some symbols not displayed correctly? |