On 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 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\in[0,1]^n\) with \(\sum_i x_i=\sum_i y_i=k\), it satisfies \[ \mathbb{E}\!\left[|A(x)\triangle A(y)|\right] \le 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.

15 pages