TY - JOUR

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

AU - Lee, Kangbok

AU - Leung, Joseph Y.T.

AU - Pinedo, Michael L.

N1 - Funding Information:
E-mail addresses: klee3@stern.nyu.edu (K. Lee), leung@cis.njit.edu (J.Y.-T. Leung), mpinedo@stern.nyu.edu (M.L. Pinedo). 1 Work supported by the Korea Research Foundation Grant KRF-2007-357-D00270. 2 Work supported in part by the NSF Grant DMI-0556010. 3 Work supported in part by the NSF Grant DMI-0555999.

PY - 2009/5/31

Y1 - 2009/5/31

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Eligibility constraints

KW - Parallel machines scheduling

KW - Semi-matching

UR - http://www.scopus.com/inward/record.url?scp=62749100498&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=62749100498&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2009.02.010

DO - 10.1016/j.ipl.2009.02.010

M3 - Article

AN - SCOPUS:62749100498

VL - 109

SP - 608

EP - 610

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 12

ER -