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

DOI10.1016/J.IPL.2009.02.010MaRDI QIDQ987836zbMATH OpenOpenAlexFDO

Authors 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 algorithmseligibility constraintsparallel machines schedulingsemi-matching

Mathematics Subject Classification ID

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

Recommendations

• Semi-matchings for bipartite graphs and load balancing.
• Semi-matchings for bipartite graphs and load balancing
• Theory and Applications of Models of Computation
• An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs
• Faster algorithms for semi-matching problems

Cites work

• An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs
• An optimal rounding gives a better approximation for scheduling unrelated machines
• Approximation algorithms for scheduling unrelated parallel machines
• scientific article; zbMATH DE number 5345854 (Why is no real title available?)
• scientific article; zbMATH DE number 5764783 (Why is no real title available?)
• Parallel machine scheduling under a grade of service provision
• Parallel machine scheduling with job assignment restrictions
• Parallel machine scheduling with nested processing set restrictions
• Scheduling parallel machines with inclusive processing set restrictions
• Semi-matchings for bipartite graphs and load balancing.
• The Competitiveness of On-Line Assignments

Cited in

(1)

• Semi-matchings for bipartite graphs and load balancing

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q987836)