|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Symmetry exploitation for Online Machine Covering with Bounded Migration | | Waldo Gálvez
; José A. Soto
; José Verschae
; | | Date: |
6 Dec 2016 | | 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.
Using a new rounding procedure specially tailored for online problems, we
design a $(4/3+varepsilon)$-competitive algorithm using migration factor
$ ilde{O}(1/varepsilon^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, a low migration factor is
achieved by carefully exploiting the highly symmetric structure obtained by our
rounding.
We also study local search algorithms for the machine covering problem, and
show that jump and swap optimality have an approximation ratio which lies in
the interval $[1.691, 1.75]$ and can be adapted to the online context with a
small constant as migration factor. Our lower bound is obtained by a nice
construction based on Sylvester’s sequence. | | Source: | arXiv, 1612.1829 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER