Abstract

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.