摘要
我们描述了适用于二分图的新依赖舍入算法。给定图 $G = (U \cup V, E)$ 的分数匹配 $x$，该算法返回一个整数解 $X$，使得每个右侧节点 $v \in V$ 至多有一条边，并且变量 $X_e$ 还满足广泛的非正相关性属性。
特别地，对于共享左侧节点 $u \in U$ 的任意边 $e_1, e_2$，变量 $X_{e_1}, X_{e_2}$ 具有 强 负相关性，即 $\mathbb{E}[X_{e_1} X_{e_2}]$ 显著低于 $x_{e_1} x_{e_2}$。
这种具有这些属性的依赖舍入方案已被用于无关机器的作业调度的近似算法，以最小化加权完成时间等其他应用。我们新的算法相比于先前的算法取得了更简单且更强的定性界限。
特别地，我们达到了负相关属性 $$\mathbb{E}[X_{e_1} X_{e_2}] \leq 0.79751 x_{e_1} x_{e_2}$$，这是对 Baveja、Qu 和 Srinivasan (2023) 的显著常数因子改进。
博主点评： 本文提出的依赖舍入算法在二分图的整数匹配中展示了强大的负相关性，这一进展为作业调度等领域的优化提供了新的思路和工具，值得深入研究与应用。