{"id":"arxiv/2606.07820","url":"https://arxiv.org/abs/2606.07820","tags":["cs.DS","math.PR"],"score":0,"title":"A note on rounding fractional matchings with constant-factor strong negative correlation","domain":"cs.DS","source":"arxiv","authors":["David G. Harris"],"reviews":0,"subject":"cs.DS","summary":"We describe new dependent-rounding algorithms for bipartite graphs. Given a fractional matching $x$ of graph $G = (U \\cup V, E)$, the algorithms return an integral solution $X$ such that each right-node $v \\in V$ has at most one edge, and where the variables $X_e$ also satisfy broad non-positive correlation properties. In particular, for any edges $e_1, e_2$ sharing a left-node $u \\in U$, the variables $X_{e_1}, X_{e_2}$ have *strong* negative-correlation, i.e. the expectation of $X_{e_1} X_{e_2}$ is significantly below $x_{e_1} x_{e_2}$. Dependent rounding schemes with these properties have…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-05","reactions":{}}