Symmetry exploitation for online machine covering with bounded migration
Author
dc.contributor.author
Gálvez, Waldo
Author
dc.contributor.author
Soto, José
Author
dc.contributor.author
Verschae, José
Admission date
dc.date.accessioned
2019-05-31T15:21:19Z
Available date
dc.date.available
2019-05-31T15:21:19Z
Publication date
dc.date.issued
2016
Cita de ítem
dc.identifier.citation
Leibniz International Proceedings in Informatics, LIPIcs, Volumen 112, 2016, Pages 32:1–32:14
Identifier
dc.identifier.issn
18688969
Identifier
dc.identifier.other
10.4230/LIPIcs.ESA.2018.32
Identifier
dc.identifier.uri
https://repositorio.uchile.cl/handle/2250/169568
Abstract
dc.description.abstract
Online models that allow recourse are highly effective in situations where classical models are
too pessimistic. One such problem is the online machine covering problem on identical machines.
In this setting, jobs arrive one by one and must be assigned to machines with the objective of
maximizing the minimum machine load. When a job arrives, we are allowed to reassign some
jobs as long as their total size is (at most) proportional to the processing time of the arriving
job. The proportionality constant is called the migration factor of the algorithm.
By rounding the processing times, which yields useful structural properties for online packing
and covering problems, we design first a simple (1.7+ε)-competitive algorithm using a migration
factor of O(1/ε) which maintains at every arrival a locally optimal solution with respect to the
Jump neighborhood. After that, we present as our main contribution a more involved (4/3 + ε)-
competitive algorithm using a migration factor of O˜(1/ε3
). At every arrival, we run an adaptation
of the Largest Processing Time first (LPT) algorithm. Since the new job can cause a complete
change of the assignment of smaller jobs in both cases, a low migration factor is achieved by
carefully exploiting the highly symmetric structure obtained by the rounding procedure.
Lenguage
dc.language.iso
en
Publisher
dc.publisher
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing