The Load Minimization Problem on cycles

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.

Año de publicación:

2022

Keywords:

• assignment
• Approximation algorithms
• routing
• network routing

Fuente:

scopus

google