Faster and simpler traversal of 0/1-polytopes
Recently, Merino and Mütze (FOCS'23+SICOMP'24) presented an algorithm for computing a Hamilton path on the skeleton of any 0/1-polytope ${\rm conv}(X)$, where $X\subseteq\{0,1\}^n$. The algorithm uses as a black box an algorithm for solving the classical linear optimization problem $\min\{w\cdot x\mid x\in X\}$ for some weight vector $w\in\mathbb{R}^n$. The resulting delay per visited vertex on the Hamilton path is only by a $\log n$ factor larger than the time to solve one instance of the optimization algorithm. In this paper, we make the Hamilton path algorithm simpler and faster. Namely,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.17590
curl -X POST /api/v1/records/arxiv/2607.17590/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.17590/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'