Number of the records: 1
Graph balancing: A special case of scheduling unrelated parallel machines
- 1.
SYSNO ASEP 0318586 Document Type C - Proceedings Paper (int. conf.) R&D Document Type Conference Paper Title Graph balancing: A special case of scheduling unrelated parallel machines Title Vyvažování grafů: Speciální případ rozvrhování nezávislých paralelních počítačů Author(s) Ebenlendr, Tomáš (MU-W) SAI, RID
Krčál, Marek (MU-W)
Sgall, Jiří (MU-W) RID, ORCID, SAISource Title Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms. - San Francisco : ACM-SIAM, 2008 - ISBN 978-0-89871-647-4 Pages s. 483-490 Number of pages 8 s. Action Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)/10./ Event date 20.01.2008-22.01.2008 VEvent location San Francisco Country US - United States Event type WRD Language eng - English Country US - United States Keywords graph ; graph balancing ; scheduling Subject RIV BA - General Mathematics R&D Projects GA201/05/0124 GA ČR - Czech Science Foundation (CSF) IAA1019401 GA AV ČR - Academy of Sciences of the Czech Republic (AV ČR) CEZ AV0Z10190503 - MU-W (2005-2011) Annotation 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, which the same processing time on either machine. We also show that even for this special case it is $NP$-hard to compute better than 1.5 approximation. Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2009
Number of the records: 1