Keyun Cheng

Reading Notes: IPL’09 Semi-matching correction on IPL’06

Title: A note on “An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs”

Conference (): Link

Journal (IPL’09): Link

Summary

This paper summarizes the approximation algorithm in IPL’06 and corrects the theoretical bounds for the algorithm. At the end, it also mentioned some solutions for general scheduling for unrelated parallel machines problem, not necessarily related to semi-matching for bipartite graphs.

Main Contributions

Details

Strength

Weakness