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 a graph \(G=(U\cup V,E)\) , the algorithms return an integral solution \(\vec{X}\) such that each right-node \(v\in V\) has at most one neighboring edge \( f \) with \(X_{f}=1\) , and the variables \(X_{e}\) also satisfy broad nonpositive-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}}\) . This algorithm is based on generating negatively correlated Exponential random variables and using them for a rounding method inspired by a contention-resolution scheme of Im and 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 et al., 2021; Im and Li, 2023; Im and Shadloo, 2020]. 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 and Li [2023].