Abstract
We describe new dependent-rounding algorithms for bipartite graphs. Given a fractional matching $x$ of graph $G = (U \cup V, E)$, the algorithms return an integral solution $X$ such that each right-node $v \in V$ has at most one edge, and where the variables $X_e$ also satisfy broad non-positive correlation properties.
In particular, for any edges $e_1, e_2$ sharing a left-node $u \in U$, the variables $X_{e_1}, X_{e_2}$ have strong negative-correlation, i.e. the expectation of $X_{e_1} X_{e_2}$ is significantly below $x_{e_1} x_{e_2}$.
Dependent rounding schemes with these properties have been used for approximation algorithms for job-scheduling on unrelated machines to minimize weighted completion times, among other applications. Our new algorithm achieves simpler and qualitatively stronger bounds compared to prior algorithms.
In particular, we achieve a negative-correlation property $$\mathbb{E}[X_{e_1} X_{e_2}] \leq 0.79751 x_{e_1} x_{e_2}$$, which is a significant constant-factor improvement over Baveja, Qu & Srinivasan (2023).
Blogger's Review: The dependent rounding algorithm proposed in this paper demonstrates strong negative correlation in integer matchings of bipartite graphs, providing new insights and tools for optimization in areas such as job scheduling, making it a significant contribution worth further exploration.