An improved randomized algorithm for finding sinks of Acyclic Unique Sink Orientations of the binary hypercube
Abstract
Acyclic Unique Sink Orientations (AUSOs) of the binary hypercube form an elegant abstraction of various optimization problems, ranging from linear programs whose feasibility region is a combinatorial hypercube, to 2-player turn-based stochastic games (2TBSGs) in which one of the players has two actions from each one of its states. The currently fastest known randomized algorithm for finding the sink of such AUSOs is the Random-Facet algorithm of Kalai (STOC 1992), and of Matoušek, Sharir and Welzl (SoCG 1992), adapted to the binary hypercube by Gärtner (RSA 2002). The expected number of vertex queries made by the algorithm is at most e2√n, where n is the dimension of the cube. We design an improved randomized sink-finding algorithm that performs an expected number of only e√((2+o(1))n) queries. This is the first improved bound for the problem in over two decades. The improved algorithm is obtained by adapting improved versions of the Random-Facet algorithm for solving general linear programs, and LP-type problems, developed by Kalai (STOC 1992), Gärtner (FOCS 1992), and by Hansen and Zwick (STOC 2015). The improved bound is not implied by these much more general algorithms. A key feature of the improved algorithm and its analysis is its simplicity. The structure of binary AUSOs enables a simpler description and a much simpler analysis of the adapted algorithm. In particular, the recurrence relations bounding the complexity of the algorithm depend on only one variable, and not two, and they can be solved using fairly straightforward techniques.
Related
- Sharp connectivity thresholds for mixed rigidity packings and improved bounds for highly connected orientations of graphs
- The AECM Algorithm for Deterministic Maximum Likelihood Direction Finding in the Presence of Gaussian Mixture Noise
- Improved Multiplayer Bandit Algorithm for Bernoulli Rewards
- An Adaptive Symplectic Proximal Point Algorithm: Faster Convergence and Improved Numerical Performance
- Accelerating the Improved Arrow--Hurwicz Iteration via the Anderson Algorithm for Steady-State Navier--Stokes Equations
BibTeX
@misc{hansen2026improved,
title = {{An improved randomized algorithm for finding sinks of Acyclic Unique Sink Orientations of the binary hypercube}},
author = {Thomas Dueholm Hansen and Uri Zwick},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.22546},
eprint = {2610.22546},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.22546},
}
RIS
TY - UNPB
TI - An improved randomized algorithm for finding sinks of Acyclic Unique Sink Orientations of the binary hypercube
AU - Thomas Dueholm Hansen
AU - Uri Zwick
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2610.22546
UR - https://arxiv.org/abs/2610.22546
AB - Acyclic Unique Sink Orientations (AUSOs) of the binary hypercube form an elegant abstraction of various optimization problems, ranging from linear programs whose feasibility region is a combinatorial hypercube, to 2-player turn-based stochastic games (2TBSGs) in which one of the players has two actions from each one of its states. The currently fastest known randomized algorithm for finding the sink of such AUSOs is the Random-Facet algorithm of Kalai (STOC 1992), and of Matoušek, Sharir and Welzl (SoCG 1992), adapted to the binary hypercube by Gärtner (RSA 2002). The expected number of vertex queries made by the algorithm is at most e^2√n, where n is the dimension of the cube. We design an improved randomized sink-finding algorithm that performs an expected number of only e^√((2+o(1))n) queries. This is the first improved bound for the problem in over two decades. The improved algorithm is obtained by adapting improved versions of the Random-Facet algorithm for solving general linear programs, and LP-type problems, developed by Kalai (STOC 1992), Gärtner (FOCS 1992), and by Hansen and Zwick (STOC 2015). The improved bound is not implied by these much more general algorithms. A key feature of the improved algorithm and its analysis is its simplicity. The structure of binary AUSOs enables a simpler description and a much simpler analysis of the adapted algorithm. In particular, the recurrence relations bounding the complexity of the algorithm depend on only one variable, and not two, and they can be solved using fairly straightforward techniques.
ER -