INVESTIGADORES
ESCALANTE Mariana Silvina
congresos y reuniones científicas
Título:
The Load Minimization Problem on cycles
Autor/es:
ESCALANTE, MARIANA SILVINA; MATAMALA, MARTIN; RAPAPORT, IVAN; TORRES, LUIS MIGUEL
Lugar:
Viña del Mar
Reunión:
Conferencia; APPLIED COMBINATORIAL OPTIMIZATION 2021-2022; 2022
Institución organizadora:
ALIO EURO
Resumen:
In this work we study the Load Minimization Problem in undirected weighted cycles. In this problem, we are given a cycle anda set of weighted origin-destination pairs. The goal is to routeall the pairs minimizing the load of the routing according to thegiven weights. We prove that the problem is NP-complete andthat it is 2-approximable. For unitary weights we present a FPTalgorithm whose parameter is a natural lower bound for the valueof the load.
