Dependent rounding with strong negative-correlation, and scheduling on unrelated machines to minimize completion time

We describe a new dependent-rounding algorithmic framework for bipartite graphs. Given a fractional assignment vec x of values to edges of graph G = (U cup V, E), the algorithms return an integral solution vec X such that each right-node v ∈ V has at most one neighboring edge f with Xf = 1, and the variables Xe also satisfy broad nonpositive-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. This algorithm is based on generating negatively-correlated Exponential random variables and using them in a contention-resolution scheme inspired by an algorithm Im & Shadloo (2020). Our algorithm gives stronger and much more flexible negative correlation properties. Dependent rounding schemes with negative correlation properties have been used for approximation algorithms for job-scheduling on unrelated machines to minimize weighted completion times (Bansal, Srinivasan, & Svensson (2021), Im & Shadloo (2020), Im & Li (2023)). Using our new dependent-rounding algorithm, among other improvements, we obtain a 1.398-approximation for this problem. This significantly improves over the prior 1.45-approximation ratio of Im & Li (2023).