Počet záznamů: 1
Graph balancing: a special case of scheduling unrelated parallel machines
- 1.
SYSNO ASEP 0424769 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název Graph balancing: a special case of scheduling unrelated parallel machines Tvůrce(i) Ebenlendr, Tomáš (MU-W) SAI, RID
Krčál, M. (CZ)
Sgall, J. (CZ)Zdroj.dok. Algorithmica. - : Springer - ISSN 0178-4617
Roč. 68, č. 1 (2014), s. 62-80Poč.str. 17 s. Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova approximation algorithms ; weighted outdegree ; orientation Vědní obor RIV BA - Obecná matematika CEP GBP202/12/G061 GA ČR - Grantová agentura ČR 1M0545 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy IAA100190902 GA AV ČR - Akademie věd Institucionální podpora MU-W - RVO:67985840 UT WOS 000329093300004 EID SCOPUS 84891887570 DOI 10.1007/s00453-012-9668-9 Anotace 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. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2014
Počet záznamů: 1