A note on "An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs"
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. (c) 2009 Elsevier B.V. All rights reserved.
approximation algorithms semi-matching parallel machines scheduling eligibility constraints