Matching with sizes (or scheduling with processing set restrictions)
Matching with sizes (or scheduling with processing set restrictions)
复制标题
DOI：
10.1016/j.dam.2011.11.003
复制
发表时间：
2014-02
期刊：
影响因子：
--
通讯作者：
P. Biró;Eric McDermid
中科院分区：
文献类型：
--
作者：
P. Biró;Eric McDermid
二分图上的匹配问题，其中的一方的实体可能有不同的大小是密切相关的处理集限制的调度问题。我们调查这两个问题之间的密切关系，并给出新的近似算法的（NP-难）的变化的问题，其中的大小的工作是有限的。具体地说，我们给出了一个近似算法，当工件的大小为1或2时，其加性误差为1，并将其推广到一个近似算法，当每个工件的大小取自集合{1，2，4，...，2 k}（对于任何常整数k）时，其加性误差为2 k− 1。我们表明，上述两个问题成为多项式时间可解的，如果处理集是嵌套的。
Matching problems on bipartite graphs where the entities on one side may have different sizes are intimately related to scheduling problems with processing set restrictions. We survey the close relationship between these two problems, and give new approximation algorithms for the (NP-hard) variations of the problems in which the sizes of the jobs are restricted. Specifically, we give an approximation algorithm with an additive error of one when the sizes of the jobs are either 1 or 2, and generalise this to an approximation algorithm with an additive error of 2 k− 1 for the case where each job has a size taken from the set {1, 2, 4,…, 2 k}(for any constant integer k). We show that the above two problems become polynomial-time solvable if the processing sets are nested.