A note on "An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs"

作者：Lee Kangbok; Leung Joseph Y T^*; Pinedo Michael L

来源：Information Processing Letters, 2009, 109(12): 608-610.

DOI：10.1016/j.ipl.2009.02.010

• Semi-matching
• Parallel machines scheduling
• Eligibility constraints
• Approximation algorithms

We point out an error in the algorithm for the Load Balanced Semi-Matching Problem presented by C.P. Low [C.P. Low, An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs, Information Processing Letters 100 (2006) 154-161]. This problem is equivalent to a parallel machine scheduling problem subject to eligibility constraints, in which each job has a pre-determined set of machines capable of processing the job.

• 出版日期2009-5-31