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

Kangbok Lee; Joseph Y.T. Leung; Michael L. Pinedo

doi:10.1016/j.ipl.2009.02.010

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

Kangbok Lee
, Joseph Y.T. Leung
, Michael L. Pinedo

Computer Science

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

Abstract

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.

Original language	English (US)
Pages (from-to)	608-610
Number of pages	3
Journal	Information Processing Letters
Volume	109
Issue number	12
DOIs	https://doi.org/10.1016/j.ipl.2009.02.010
State	Published - May 31 2009

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Keywords

Approximation algorithms
Eligibility constraints
Parallel machines scheduling
Semi-matching

Access to Document

10.1016/j.ipl.2009.02.010

Cite this

@article{3b9c06f647b04743a66fc751e5f3ab15,

title = "A note on {"}An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs{"}",

abstract = "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.",

keywords = "Approximation algorithms, Eligibility constraints, Parallel machines scheduling, Semi-matching",

author = "Kangbok Lee and Leung, \{Joseph Y.T.\} and Pinedo, \{Michael L.\}",

note = "Funding Information: E-mail addresses: [email protected] (K. Lee), [email protected] (J.Y.-T. Leung), [email protected] (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.",

year = "2009",

month = may,

day = "31",

doi = "10.1016/j.ipl.2009.02.010",

language = "English (US)",

volume = "109",

pages = "608--610",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "12",

}

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: [email protected] (K. Lee), [email protected] (J.Y.-T. Leung), [email protected] (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 - https://www.scopus.com/pages/publications/62749100498

UR - https://www.scopus.com/pages/publications/62749100498#tab=citedBy

U2 - 10.1016/j.ipl.2009.02.010

DO - 10.1016/j.ipl.2009.02.010

M3 - Article

AN - SCOPUS:62749100498

SN - 0020-0190

VL - 109

SP - 608

EP - 610

JO - Information Processing Letters

JF - Information Processing Letters

IS - 12

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this