O problema da máxima interseção de k-subconjuntos

Maximum k-subset problem

dc.creatorBogue, Eduardo Theodoro, 1990-
dc.date2014
dc.date2017-04-02T05:32:33Z
dc.date2017-06-09T15:07:13Z
dc.date2017-04-02T05:32:33Z
dc.date2017-06-09T15:07:13Z
dc.date.accessioned2018-03-29T02:19:37Z
dc.date.available2018-03-29T02:19:37Z
dc.identifierBOGUE, Eduardo Theodoro. O problema da máxima interseção de k-subconjuntos. 2014. 51 f. Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação, Campinas, SP. Disponível em: <http://www.bibliotecadigital.unicamp.br/document/?code=000931530>. Acesso em: 2 abr. 2017.
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/275507
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1314223
dc.descriptionOrientadores: Cid Carvalho de Souza, Eduardo Candido Xavier
dc.descriptionDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação
dc.descriptionResumo: Neste projeto, nós estudamos o Problema da Máxima Interseção de k-Subconjuntos (kMIS). Dado um inteiro k, um conjunto base U e uma coleção S de subconjuntos de U, o problema kMIS consiste em selecior k subconjuntos distintos S1, S2, ... , Sk em S cujo tamanho da interseção de |S1 ? S2 ? ... ? Sk| seja máxima. Trata-se de um problema NP-difícil e difícil de ser aproximado que ocorre em aplicações de áreas como biologia computacional e privacidade de dados. Até o nosso conhecimento, nenhum método exato foi proposto para resolver este problema. Neste trabalho, introduzimos cinco formulações de programação linear inteira para o problema, sendo três baseadas no método de Branch-and-Bound e duas no método de Branch-and-Cut. Além disso, uma heurística gulosa e uma meta-heurística GRASP foram desenvolvidas com o intuito de gerar bons limitantes inferiores. A heurística GRASP desenvolvida foi capaz de encontrar soluções muito próximas da solução ótima. Ademais, introduzimos um método muito eficiente de pré-processamento para reduzir o tamanho da entrada. Experimentos computacionais foram realizados de forma a analisar o desempenho dos modelos de programação linear inteira em questão, demonstrando que os modelos baseados no método de Branch-and-Cut obtiveram melhores resultados
dc.descriptionAbstract: In this project, we study the Maximum k-Subset Intersection problem (kMIS). Given an integer k, a ground set U and a collection S of subsets of U, the kMIS problem is to select k distinct subsets S1, S2, ... , Sk in S whose intersection size |S1 ? S2 ? ... ? Sk| is maximum. The kMIS problem is NP-hard and hard to approximate and occurs in areas of applications such as computational biology and data privacy. To the best of our knowledge, no exact method was proposed to solve this problem. In this work, we introduce five integer linear programming formulations for the problem, three using a simple Branch-and-Bound method and two using a Branch-and-Cut method. We also present a greedy heuristic and a metaheuristic GRASP developed in order to generate good lower bounds. The heuristic GRASP developed was able to find solutions very close to the optimal ones. Furthermore, we introduce a very efficient preprocessing procedure to reduce the size of the input. Computational experiments were performed in order to analyze the performance of the integer linear programming models in question, showing that the Branch-and-Cut models performed better
dc.descriptionMestrado
dc.descriptionCiência da Computação
dc.descriptionMestre em Ciência da Computação
dc.format51 f. : il.
dc.formatapplication/octet-stream
dc.publisher[s.n.]
dc.subjectOtimização combinatória
dc.subjectProgramação linear
dc.subjectAlgoritmos em grafos
dc.subjectCombinatorial optimization
dc.subjectLinear programming
dc.subjectGraph algorithms
dc.titleO problema da máxima interseção de k-subconjuntos
dc.titleMaximum k-subset problem
dc.typeTesis


Este ítem pertenece a la siguiente institución