On the weighted Minimum Clique Routing Problem

ESCALANTE, MARIANA SILVINA; MATAMALA, MARTIN; RAPAPORT, IVAN; TOLOMEI, PAOLA; TORRES, LUIS MIGUEL

Buenos Aires

Conferencia; XXI LATIN IBERO-AMERICAN CONFERENCE ON OPERATIONS RESEARCH; 2022

CLAIO- Universidad Nacional de Buenos Aires

Given an undirected graph $G=(V,E)$ and a set of demands $D$, each of them specified by a source $s_p \in V$, a target $t_p \in V$ and a weight $w_p \in Z$, the (weighted) Minimum Clique Routing problem (w-MCRP) asks for finding a path for each demand, connecting its source to its target. The aim is to minimize the maximum weight of a clique in the edge intersection graph of these paths, where the weight of each path is the weight of the corresponding demand. The particular case when $G$ is a cycle and all weights are equal to one was addressed in [1] in the context of routing and wavelength assignment in an optical ring network without wavelength conversion capabilities. In this work, we study the weighted problem in networks with a ring topology. We prove that w-MCRP is NP-hard in cycles and present two approximation algorithms for this problem, obtained by extending the results of previous works for the unweighted case. The first one is a 2-approximation algorithm based solely on graph combinatorial techniques. The second one is an extension of a 3/2-approximation algorithm presented in [1] which is based on solving the linear relaxation of an IP formulation of the problem and afterward applying a rounding scheme.