{"id":"arxiv/2607.17590","url":"https://arxiv.org/abs/2607.17590","tags":["cs.DS","cs.DM","math.CO"],"score":0,"title":"Faster and simpler traversal of 0/1-polytopes","domain":"cs.DS","source":"arxiv","authors":["Jiří Fink","Petr Hladík","Arturo Merino","Ondřej Mička","Torsten Mütze"],"reviews":0,"subject":"cs.DS","summary":"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,…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-20","reactions":{}}