Por favor, use este identificador para citar o enlazar este ítem: http://repositorio.ufc.br/handle/riufc/21531
Tipo: Dissertação
Título : O problema da atribuição conexa
Título en inglés: The connected assignment problem
Autor : Soares, Joel Cruz
Tutor: Campêlo Neto, Manoel Bezerra
Palabras clave : Rede de comunicações móveis;Complexidade computacional;Programação inteira;Combinatória poliédrica;Heurística
Fecha de publicación : 2016
Citación : SOARES, Joel Cruz. O problema da atribuição conexa. 2016. 96 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal do Ceará, Fortaleza, 2016.
Resumen en portugués brasileño: Apresentamos um problema com aplicação em alocação de recursos em redes de comunicações móveis, que denominamos de Problema da Atribuição Conexa em Vetores (ACV). Este problema tem como entrada um conjunto de símbolos $I=\{1,2,\dots,M\}$, um vetor $v$ indexado por $J=\{1,2,\dots,N\}$, e um valor de ganho $\rho_{ij}$ ao alocar $i \in I$ à posição $j$ de $v$. Desejamos encontrar uma atribuição dos símbolos ao vetor que tenha o maior ganho possível, sob a restrição de que símbolos repetidos sejam adjacentes no vetor. Demonstramos que ACV é um problema NP-Difícil a partir de uma redução do Problema de Recoloração Convexa de Caminhos (RCC). Apresentamos um algoritmo aproximativo para um caso particular deste problema ($k$-ACV). Propomos três formulações de Programação Inteira e comparamos teoricamente suas relaxações lineares. Estudamos o poliedro $\mathcal{P}$ associado à formulação mais forte. Determinamos todas as desigualdades indutoras de facetas com lado direito igual a 1 e mostramos que elas, junto com as restrições de não-negatividade, descrevem $\mathcal{P}$ quando $M=2$ ou $N=2$. Generalizamos essa classe de desigualdades válidas, mantendo a propriedade de que induzem facetas. Ao final, propomos 5 heurísticas para o problema e as comparamos através de resultados de experimentos computacionais.
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.
URI : http://www.repositorio.ufc.br/handle/riufc/21531
Aparece en las colecciones: DCOMP - Dissertações defendidas na UFC

Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
2016_dis_jcsoares.pdf722,04 kBAdobe PDFVisualizar/Abrir


Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.