Graph balancing: a special case of scheduling unrelated parallel machines

0424769 - MÚ 2014 RIV US eng J - Journal Article
Ebenlendr, Tomáš - Krčál, M. - Sgall, J.
Graph balancing: a special case of scheduling unrelated parallel machines.
Algorithmica. Roč. 68, č. 1 (2014), s. 62-80. ISSN 0178-4617. E-ISSN 1432-0541
R&D Projects: GA ČR GBP202/12/G061; GA MŠMT(CZ) 1M0545; GA AV ČR IAA100190902
Institutional support: RVO:67985840
Keywords : approximation algorithms * weighted outdegree * orientation
Subject RIV: BA - General Mathematics
Impact factor: 0.791, year: 2014
http://link.springer.com/article/10.1007%2Fs00453-012-9668-9

We design a 1.75-approximation algorithm for a special case of scheduling parallel machines to minimize the makespan, namely the case where each job can be assigned to at most two machines, with the same processing time on either machine. (This is a special case of so-called restricted assignment, where the set of eligible machines can be arbitrary for each job.) This is the first improvement of the approximation ratio 2 of Lenstra, Shmoys, and Tardos (Math. Program. 46:259–271, 1990), to a smaller constant for any special case with unbounded number of machines and unbounded processing times. We conclude by showing integrality gaps of several relaxations of related problems.
Permanent Link: http://hdl.handle.net/11104/0230789