A note on semi-online machine covering
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F06%3A00041413" target="_blank" >RIV/67985840:_____/06:00041413 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
A note on semi-online machine covering
Original language description
In the machine cover problem we are given $m$ machines and $n$ jobs to be assigned (scheduled) so that the smallest load of a machine is as large as possible. A semi-online algorithms is given in advance the optimal value of the smallest load for the given instance, and then the jobs are scheduled one by one as they arrive, without any knowledge of the following jobs. We present a deterministic algorithm with competitive ratio $11/6/leq 1.834$ for machine covering with any number of machines and a lowerbound showing that no deterministic algorithm can have a competitive ratio below $43/24/geq 1.791$.
Czech name
O semi-online pokrývání počítačů
Czech description
Článek studuje semi-online pokrývání počítačů.
Classification
Type
D - Article in proceedings
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2006
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the 3rd Workshop on Approximation and Online Algorithms (WAOA)
ISBN
3-540-32207-8
ISSN
—
e-ISSN
—
Number of pages
9
Pages from-to
110-118
Publisher name
Springer
Place of publication
Berlin
Event location
Palma de Mallorca
Event date
Oct 6, 2005
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—