The Load Minimization Problem on cycles

ESCALANTE, MARIANA; TOLOMEI, PAOLA; MATAMALA, MARTÍN; RAPAPORT, IVÁN

Viña del Mar

Congreso; Joint ALIO/EURO International Conference on Applied Combinatorial Optimization; 2022

In this work we study the Load Minimization Problem in undirected weighted cycles. In this problem, we are given a cycle and a set of weighted origin-destination pairs. The goal is to route all the pairs minimizing the load of the routing according to the given weights. We prove that the problem is NP-complete and that it is 2-approximable. For unitary weights we present a FPT algorithm whose parameter is a natural lower bound for the value of the load.