O problema da máxima interseção de k-subconjuntos
Eduardo Theodoro Bogue
DISSERTAÇÃO
T/UNICAMP B634p
[Maximum k-subset problem]
Campinas, SP : [s.n.], 2014.
51 f. : il.
Orientadores: Cid Carvalho de Souza, Eduardo Candido Xavier
Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação
Resumo: 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 ? ......
Ver mais
Resumo: 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
Ver menos
Abstract: 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...
Ver mais
Abstract: 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
Ver menos
Souza, Cid Carvalho de, 1963-
Orientador
Xavier, Eduardo Candido, 1979-
Coorientador
Frota, Yuri Abitbol de Menezes, 1976-
Avaliador
Usberti, Fábio Luiz, 1982-
Avaliador
O problema da máxima interseção de k-subconjuntos
Eduardo Theodoro Bogue
O problema da máxima interseção de k-subconjuntos
Eduardo Theodoro Bogue
Exemplares
Nº de exemplares: 2
Não existem reservas para esta obra