An improved randomized algorithm for finding sinks of Acyclic Unique Sink Orientations of the binary hypercube
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.22546
curl -X POST /api/v1/records/arxiv/2610.22546/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.22546/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'