O problema da atribuição conexa

Detalhes bibliográficos
Ano de defesa: 2016
Autor(a) principal: Soares, Joel Cruz
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Não Informado pela instituição
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: http://www.repositorio.ufc.br/handle/riufc/21531
Resumo: 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.