Multiprocessor jobs, preemptive schedules, and one-competitive online algorithms

J. Sgall, G. Woeginger

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

Samenvatting

We study online preemptive makespan minimization on m parallel machines, where the (multiprocessor) jobs arrive over time and have widths from some fixed set W ¿ {1,2,…,m}. For every number m of machines we concisely characterize all the sets W for which there is a 1-competitive fully online algorithm and all the sets W for which there is a 1-competitive nearly online algorithm.
Originele taal-2Engels
TitelApproximation and Online Algorithms (12th International Workshop, WAOA 2014, Wrocław, Poland, September 11-12, 2014, Revised Selected Papers)
RedacteurenE. Bampis, O. Svensson
Plaats van productieDordrecht
UitgeverijSpringer
Pagina's236-247
ISBN van geprinte versie978-3-319-18262-9
DOI's
StatusGepubliceerd - 2015
Evenement12th International Workshop on Approximation and Online Algorithms (WOA 2012) - Wroclaw, Polen
Duur: 11 sep 201412 sep 2014
Congresnummer: 12

Publicatie series

NaamLecture Notes in Computer Science
Volume8952
ISSN van geprinte versie0302-9743

Congres

Congres12th International Workshop on Approximation and Online Algorithms (WOA 2012)
Verkorte titelWOA 2012
LandPolen
StadWroclaw
Periode11/09/1412/09/14
Ander12th International Workshop on Approximation and Online Algorithms

Vingerafdruk Duik in de onderzoeksthema's van 'Multiprocessor jobs, preemptive schedules, and one-competitive online algorithms'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Sgall, J., & Woeginger, G. (2015). Multiprocessor jobs, preemptive schedules, and one-competitive online algorithms. In E. Bampis, & O. Svensson (editors), Approximation and Online Algorithms (12th International Workshop, WAOA 2014, Wrocław, Poland, September 11-12, 2014, Revised Selected Papers) (blz. 236-247). (Lecture Notes in Computer Science; Vol. 8952). Springer. https://doi.org/10.1007/978-3-319-18263-6_20