Graph balancing: A special case of scheduling unrelated parallel machines

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F08%3A00318586" target="_blank" >RIV/67985840:_____/08:00318586 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Graph balancing: A special case of scheduling unrelated parallel machines
Original language description
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.
Czech name
Vyvažování grafů: Speciální případ rozvrhování nezávislých paralelních počítačů
Czech description
Článek navrhuje a analyzuje algoritmy a dolní odhady pro vyvažování grafů. Jde o speciální případ rozvrhování nezávislých paralelních počítačů.

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2008
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms
ISBN
978-0-89871-647-4
ISSN
—
e-ISSN
—
Number of pages
8
Pages from-to
—
Publisher name
ACM-SIAM
Place of publication
San Francisco
Event location
San Francisco
Event date
Jan 20, 2008
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)