Graph balancing: a special case of scheduling unrelated parallel machines

0424769 - MÚ 2014 RIV US eng J - Článek v odborném periodiku
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
Grant CEP: GA ČR GBP202/12/G061; GA MŠMT(CZ) 1M0545; GA AV ČR IAA100190902
Institucionální podpora: RVO:67985840
Klíčová slova: approximation algorithms * weighted outdegree * orientation
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 0.791, rok: 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.
Trvalý link: http://hdl.handle.net/11104/0230789