Full text
| |
| Author(s): |
Eduardo Theodoro Bogue
Total Authors: 1
|
| Document type: | Master's Dissertation |
| Press: | Campinas, SP. |
| Institution: | Universidade Estadual de Campinas (UNICAMP). Instituto de Computação |
| Defense date: | 2014-03-27 |
| Examining board members: |
Cid Carvalho de Souza;
Yuri Abitbol de Menezes Frota;
Fábio Luiz Usberti
|
| Advisor: | Cid Carvalho de Souza; Eduardo Candido Xavier |
| 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 (AU) | |
| FAPESP's process: | 12/08298-6 - Maximum k-Subset Intersection Problem |
| Grantee: | Eduardo Theodoro Bogue |
| Support Opportunities: | Scholarships in Brazil - Master |