An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs

DOI10.1016/j.ipl.2006.06.004zbMath1185.05116OpenAlexW2047495487MaRDI QIDQ845858

Chor-Ping Low

Publication date: 29 January 2010

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

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

zbMATH Keywords

bipartite graphsNP-hardload balancingapproximation algorithmssemi-matching

Mathematics Subject Classification ID

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)

Related Items (3)

Distributed backup placement in networks ⋮ A note on ``An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs ⋮ Faster Algorithms for Semi-Matching Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for scheduling unrelated parallel machines
• An efficient retrieval selection algorithm for video servers with random duplicated assignment storage technique.
• TWO THEOREMS IN GRAPH THEORY
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Algorithms and Data Structures

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