Advanced search
Start date
Betweenand


Maximum k-subset problem

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:
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