Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/76485
Type: Artigo de periódico
Title: A note on a Maximum k-Subset Intersection problem
Author: Xavier, EC
Abstract: Consider the following problem which we call Maximum k-Subset Intersection (MSI): Given a collection C = {S-1 . . . . . S-m} of m subsets over a finite set of elements epsilon = {e(1) . . . . . e(n)}(,) and a positive integer k, the objective is to select exactly k subsets S-j1 . . . . .S-jk whose intersection size vertical bar S-j1 boolean AND . . . boolean AND S-jk vertical bar is maximum. In [2], Clifford and Popa (2011) studied a related problem and left as an open problem the status of the MSI problem. In this paper we show that this problem is hard to approximate. (c) 2012 Elsevier B.V. All rights reserved.
Subject: Approximation algorithms
Combinatorial problems
Subset intersection
Country: Holanda
Editor: Elsevier Science Bv
Rights: fechado
Identifier DOI: 10.1016/j.ipl.2012.03.007
Date Issue: 2012
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
WOS000303959300002.pdf105.32 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.