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

Research output: Contribution to journalArticlepeer-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 languageEnglish (US)
Pages (from-to)608-610
Number of pages3
JournalInformation Processing Letters
Volume109
Issue number12
DOIs
StatePublished - 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

Fingerprint Dive into the research topics of 'A note on "An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs"'. Together they form a unique fingerprint.

Cite this