在图调度问题中，我们需要在离散时间步骤上调度给定的边的多重集合，使得在每个步骤中，边的集合形成一个匹配。目标是最小化加权群体完成时间的总和，其中群体是一组边，当最后一条边被调度时，该群体完成。
该问题的两个流行变体是Coflow调度和数据迁移。我们的主要成果是将最近的迭代取整方法从Coflow调度扩展到一般的图调度问题，基本上对应于二分图的情况。这为假设OPT很大的渐进设置提供了一个本质上紧的 $(2+\varepsilon)$ 近似。
为此，我们依赖于一般匹配的多面体技术，特别是奇集不等式，以及关于多重图中边着色的图论结果。数据迁移的最新近似算法是 $(1 + \varphi)$ 近似，当OPT较小时效果更佳。结合我们的主要结果与这一最优算法，我们在任何情况下都获得了数据迁移近似率的提升。
博主点评： 本文通过扩展迭代取整方法，成功提升了图调度问题的近似效率，为数据迁移和Coflow调度提供了新的理论支持，展示了图论与多面体方法结合的强大潜力。此研究为优化复杂系统的调度问题提供了新的视角。