Title: Approximation Algorithms for Scheduling Unrelated Parallel Machines
Conference (Mathematical Programming’1990): Link
Journal (): Link
This paper (1) presents a 2-approximation algorithms for scheduling unrelated parallel machines problem, which serves as an important baseline for future works; (2) Proofs that there does not exist polynomial 3/2-approximation algorithms
Rounding theorem
2-approximation algorithms