Artículos de revistas
A note on a Maximum k-Subset Intersection problem
Registro en:
Information Processing Letters. Elsevier Science Bv, v. 112, n. 12, n. 471, n. 472, 2012.
0020-0190
WOS:000303959300002
10.1016/j.ipl.2012.03.007
Autor
Xavier, EC
Institución
Resumen
Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) 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. 112 12 471 472 Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)