Dependent rounding with strong negative-correlation, and scheduling on unrelated machines to minimize completion time
share
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 Y_f = 1, and where the variables Y_e also satisfy broad nonpositive-correlation properties. In particular, for any edges e_1, e_2 sharing a left-node u ∈ U, the variables Y_e_1, Y_e_2 have strong negative-correlation properties, i.e. the expectation of Y_e_1 Y_e_2 is significantly below y_e_1 y_e_2. This algorithm is a refinement of a dependent-rounding algorithm of Im & Shadloo (2020) based on simulation of Poisson processes. Our algorithm allows greater flexibility, in particular, it allows “irregular” fractional assignments, and it gives more refined bounds on the negative correlation. 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.407-approximation for this problem. This significantly improves over the prior 1.45-approximation ratio of Im Li (2023).
READ FULL TEXT