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 ⃗ x of values to edges of a graph G = (U ∪ V, E), the algorithms return an integral solution ⃗ X such that each right-node v ∈ 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 ∈ U , the variables X e1 , X e2 have strong negative correlation, i.e. the expectation of

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 & 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).

• This is an extended version of a paper appearing in the 2024 annual ACM-SIAM Symposium on Discrete Algorithms (SODA). It includes more details about the numerical analysis and slightly improved computation of the approximation ratio.