On Rounding on the Hypersimplex

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.