{"ID":2921567,"CreatedAt":"2026-06-02T02:42:49.606572591Z","UpdatedAt":"2026-06-03T04:17:48.870468959Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.00996","arxiv_id":"2606.00996","title":"Constant-Stretch Rounding on the Hypersimplex","abstract":"We study correlated rounding on the hypersimplex, the base polytope of the uniform matroid. For each point $x$ in the hypersimplex, the goal is to sample a $k$-subset $A(x)$ with marginals $x$, while coupling the samples for all choices of $x$ so that nearby inputs produce nearby sets. We give a constant-stretch scheme. Our scheme samples the maximum-entropy $k$-subset distribution with prescribed marginals using a common random ordering and common uniform thresholds. For every $x,y\\in[0,1]^n$ with $\\sum_i x_i=\\sum_i y_i=k$, it satisfies $\\mathbb{E}[|A(x)\\triangle A(y)|]\\le 6\\|x-y\\|_1$. This improves the previous $O(\\log k)$ bound for hypersimplex correlated rounding and answers an open question raised by Naor, Raju, Shetty, Srinivasan, Valieva, and Wajc. By adding dummy coordinates, the same result gives stretch at most $12$ for the at-most-$k$ polytope. The proof was found in a GPT 5.5 Pro Extended conversation prompted by the authors, and Codex was used to help assemble the manuscript under the authors' supervision.","short_abstract":"We study correlated rounding on the hypersimplex, the base polytope of the uniform matroid. For each point $x$ in the hypersimplex, the goal is to sample a $k$-subset $A(x)$ with marginals $x$, while coupling the samples for all choices of $x$ so that nearby inputs produce nearby sets. We give a constant-stretch scheme...","url_abs":"https://arxiv.org/abs/2606.00996","url_pdf":"https://arxiv.org/pdf/2606.00996v1","authors":"[\"Nima Anari\",\"Alireza Haqi\",\"Eric Ma\"]","published":"2026-05-31T04:24:33Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}