2026/06/05 by David G. Harris
#cs.DS #math.PR
We describe new dependent-rounding algorithms for bipartite graphs. Given a fractional matching x of graph G = (U ∪ V, E), the algorithms return an integral solution X such that each right-node v ∈ V has at most one edge, and where the variables Xe also satisfy broad non-positive correlation properties. In particular, for any edges e1, e2 sharing a left-node u ∈ U, the variables Xe1, Xe2 have *strong* negative-correlation, i.e. the expectation of Xe1 Xe2 is significantly below xe1 xe2. Dependent rounding schemes with these properties have been used for a approximation algorithms for job-scheduling on unrelated machines to minimize weighted completion times, among other applications. Our new algorithm achieves simpler and qualitatively stronger bounds compared to prior algorithms. In particular, we achieve a negative-correlation property \mathbb E[Xe1 Xe2] ≤ 0.79751 xe1 xe2, which is a significant constant-factor improvement over Baveja, Qu & Srinivasan (2023).