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

arXiv: https://arxiv.org/abs/2308.07476 · HTML: https://mlsanity.com/paper/2308.07476/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Aug 2023.

## Built on by (most cited first, 1 of 1)

- [Learning-Augmented Online Scheduling with Parsimonious Preemption](https://mlsanity.com/paper/2605.23255/) (2026)

## Abstract (arXiv)

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