在多配对调度问题中，给定一个带权边的图，需要构造该图的周期匹配序列，使得同一条边在相邻两次出现之间的加权等待时间的最大值最小化。该问题属于 NP 难，涵盖了竹园修剪问题（Bamboo Garden Trimming），其动机来源于为复杂社交群体安排两两会面的需求。我们提出了一种 $4 G^*$ 算法，突破了此前的上界 $3+\sqrt{5}\approx5.236$。该算法的设计灵感来源于对竹园修剪问题最优的期限驱动启发式方法，利用图的结构特性在每个截止时间前选择匹配，以保证整体等待时间的上界得到改进。
该算法的核心步骤包括：
- 为每条边计算其权重对应的截止时间；
- 按截止时间的升序遍历，贪心选择不冲突的边构成当前匹配；
- 重复上述过程直至形成完整的周期调度。
理论分析表明，算法在最坏情况下的最大加权等待时间不超过 $4 G^*$，从而实现了对已有界的显著提升。
点评