O problema da atribuição conexa

Abstract

We present a problem with application in resource allocation in mobile networks, that we name Connected Assignment in Arrays (CAA). This problem has as input a set of symbols $I=\{1,2,\dots,M\}$, an array $v$ indexed by $J=\{1,2,\dots,N\}$, and a gain value $\rho_{ij}$ of allocating $i \in I$ to position $j$ of $v$. We want to find an assignment of symbols to positions so as to maximize the gain, under the constraint that repeated symbols are adjacent in the array. We demonstrate that CAA is an NP-Hard problem by a reduction from the Convex Path Recoloring Problem (CPR). We present an approximate algorithm for a particular case of this problem ($k$-CAA). We propose three ILP formulations and theoretically compare their linear relaxation. We study the polyhedron $\mathcal{P}$ associated with the tightest formulation. We determine all facet-defining inequalities with right-hand side equal to 1 and show that they suffice, together with the non-negativeness constraints, to describe $\mathcal{P}$ when $M=2$ or $N=2$. We generalize this class of valid inequalities while keeping the property of being facet inducing. Finally, we propose 5 heuristics for the problem and compare them by results of computational experiments.