Dependent rounding with strong negative-correlation, and scheduling on unrelated machines to minimize completion time
David G. Harris · Society for Industrial and Applied Mathematics eBooks · 2024
We describe a new dependent-rounding algorithmic framework for bipartite graphs. Given a fractional assignment y of values to edges of graph G = (U ∪ V,E) the algorithms return an integral solution Y such that each right-node v ∈ V has at most one neighboring edge f with Yf = 1, and where the variables Ye also satisfy broad nonpositive-correlation properties. In particular, for any edges e1,e2 sharing a left-node u ∈ U, the variables Ye1, Ye2 have strong negative-correlation properties, i.e. the expectation of Ye1 Ye2 is significantly below ye1 ye2.