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

DOI10.1016/J.IPL.2009.02.010zbMath1217.05187OpenAlexW2047109035MaRDI QIDQ987836

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

Publication date: 16 August 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2009.02.010

zbMATH Keywords

approximation algorithmsparallel machines schedulingeligibility constraintssemi-matching

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Approximation algorithms for scheduling unrelated parallel machines
• An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs
• Parallel machine scheduling under a grade of service provision
• An optimal rounding gives a better approximation for scheduling unrelated machines
• Parallel machine scheduling with nested processing set restrictions
• Scheduling parallel machines with inclusive processing set restrictions
• The Competitiveness of On-Line Assignments
• Parallel machine scheduling with job assignment restrictions
• Algorithms and Data Structures

This page was built for publication: A note on ``An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs