# On Rounding on the Hypersimplex

arXiv: https://arxiv.org/abs/2606.00996 · HTML: https://mlsanity.com/paper/2606.00996/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 May 2026.

## Built on by (most cited first, 1 of 1)

- [A Deterministic Constant-Competitive Algorithm for Dynamic Mixture-of-Experts Serving](https://mlsanity.com/paper/2608.16947/) (2026)

## Abstract (arXiv)

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 conditional constant-stretch results for the natural maximum-entropy sequential scheme, based on a conjectured spectral property of the covariance matrix of the maximum-entropy distribution over (k)-subsets; this conjecture has been extensively tested numerically. Under this property, the scheme samples the maximum-entropy (k)-subset distribution with prescribed marginals using a common random ordering and common uniform thresholds. For every (x,y∈[0,1]n) with (sumi xi=sumi yi=k), it satisfies [ mathbbE!left[|A(x)triangle A(y)|right] ≤ 6|x-y|1 . ] Thus, conditional on the spectral hypothesis, the previous (O(log k)) bound for hypersimplex correlated rounding would improve to a constant and the open question raised by Naor, Raju, Shetty, Srinivasan, Valieva, and Wajc would have a positive answer. By adding dummy coordinates, the same conditional result gives stretch at most (12) for the at-most-(k) polytope.