2023/08/14 by Harris, David G. · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2308.07476
We describe a new dependent-rounding algorithmic framework for bipartite graphs. Given a fractional assignment x of values to edges of 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 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).