Go backward to 28 AOF Cube ProgrammingGo up to 5 Optimization |
XHTML 1.0 |

Input: | An oracle for a function
σ: {0,1} defining a
US-orientation of the graph of the ^{d} → {+,-}^{d}d-cube |
---|---|

Output: | The sink of the orientation |

Status (general): | Open |
---|---|

Status (fixed dim.): | Constant time |

Szabó and Welzl [63] describe a randomized algorithm
solving the problem in an expected number of
O(α oracle calls with
^{d})α=sqrt(43/20)<1.467 and a deterministic algorithm that
needs O(1.61 oracle calls. Plugging an optimal algorithm
for the three-dimensional case (found by Günter Rote) into their
algorithm, Szabó and Welzl even obtain an ^{d})O(1.438
randomized algorithm.
^{d})The problem not only generalizes Problem 28, but also certain linear complementary problems and smallest enclosing ball problems. In fixed dimension the problem is trivial by mere enumeration. |

Related problems: | 28 |
---|

Why are some symbols not displayed correctly? |