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

DOI10.1016/J.IPL.2006.06.004MaRDI QIDQ845858zbMATH OpenOpenAlexFDO

Authors 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

approximation algorithmsload balancingNP-hardbipartite graphssemi-matching

Mathematics Subject Classification ID

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

Recommendations

• Theory and Applications of Models of Computation
• Distributed 2-approximation algorithm for the semi-matching problem
• Brief announcement: Distributed approximations for the semi-matching problem
• On the distributed complexity of the semi-matching problem
• Semi-matchings for bipartite graphs and load balancing

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1759466 (Why is no real title available?)
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• An efficient retrieval selection algorithm for video servers with random duplicated assignment storage technique.
• Approximation algorithms for scheduling unrelated parallel machines
• Network flows. Theory, algorithms, and applications.
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Semi-matchings for bipartite graphs and load balancing.
• TWO THEOREMS IN GRAPH THEORY

Cited in

(9)

• Semi-matchings for bipartite graphs and load balancing
• Minimizing maximum weight of subsets of a maximum matching in a bipartite graph
• A Combinatorial Approximation Algorithm for Graph Balancing with Light Hyper Edges
• 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
• Distributed 2-approximation algorithm for the semi-matching problem
• Brief announcement: Distributed approximations for the semi-matching problem
• Theory and Applications of Models of Computation

This page was built for publication: 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 Q845858)