Muestra métricas de impacto externas asociadas a la publicación. Para mayor detalle:
| Indexado |
|
||
| DOI | 10.4230/LIPICS.ICALP.2021.42 | ||
| Año | 2021 | ||
| Tipo |
Citas Totales
Autores Afiliación Chile
Instituciones Chile
% Participación
Internacional
Autores
Afiliación Extranjera
Instituciones
Extranjeras
We formalize the concept of additive approximation schemes and apply it to load balancing problems on identical machines. Additive approximation schemes compute a solution with an absolute error in the objective of at most ϵh for some suitable parameter h and any given ϵ > 0. We consider the problem of assigning jobs to identical machines with respect to common load balancing objectives like makespan minimization, the Santa Claus problem (on identical machines), and the envy-minimizing Santa Claus problem. For these settings we present additive approximation schemes for h = pmax, the maximum processing time of the jobs. Our technical contribution is two-fold. First, we introduce a new relaxation based on integrally assigning slots to machines and fractionally assigning jobs to the slots. We refer to this relaxation as the slot-MILP. While it has a linear number of integral variables, we identify structural properties of (near-)optimal solutions, which allow us to compute those in polynomial time. The second technical contribution is a local-search algorithm which rounds any given solution to the slot-MILP, introducing an additive error on the machine loads of at most ϵ · pmax.
| Ord. | Autor | Género | Institución - País |
|---|---|---|---|
| 1 | Buchem, Moritz | Hombre |
Universiteit Maastricht - Países Bajos
|
| 2 | Rohwedder, Lars | Hombre |
Ecole Polytechnique Fédérale de Lausanne - Suiza
|
| 3 | Vredeveld, Tjark | Hombre |
Universiteit Maastricht - Países Bajos
|
| 4 | Wiese, Andreas | Hombre |
Universidad de Chile - Chile
|
| Fuente |
|---|
| Fondo Nacional de Desarrollo Científico y Tecnológico |
| Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung |