Maximum subset intersection

Raphaël Clifford; Alexandru Popa

doi:10.1016/j.ipl.2010.12.003

Maximum subset intersection

Raphaël Clifford, Alexandru Popa

Department of Computer Science

Research output: Contribution to journal › Article

12 Citations (Scopus)

Abstract

Consider the following problem. Given u sets of sets A₁, ⋯,A_u with elements over a universe E={e₁,⋯, e_n}, the goal is to select exactly one set from each of A ₁,⋯,A_u in order to maximize the size of the intersection of the sets. In this paper we present a gap-preserving reduction from Max-Clique which enables us to show that our problem cannot be approximated within an n^1-ε multiplicative factor, for any ε>0, unless P=NP (Zuckerman, 2006 [12]).

Original language	English
Pages (from-to)	323-325
Number of pages	3
Journal	Information Processing Letters
Volume	111
Issue number	7
DOIs	https://doi.org/10.1016/j.ipl.2010.12.003
Publication status	Published - Mar 1 2011

Fingerprint

Keywords

Approximation algorithms
Combinatorial problems

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Cite this

Clifford, R., & Popa, A. (2011). Maximum subset intersection. Information Processing Letters, 111(7), 323-325. https://doi.org/10.1016/j.ipl.2010.12.003

@article{0990422e1fad4b8a8d7cc362128ad145,

title = "Maximum subset intersection",

abstract = "Consider the following problem. Given u sets of sets A1, ⋯,Au with elements over a universe E={e1,⋯, en}, the goal is to select exactly one set from each of A 1,⋯,Au in order to maximize the size of the intersection of the sets. In this paper we present a gap-preserving reduction from Max-Clique which enables us to show that our problem cannot be approximated within an n1-ε multiplicative factor, for any ε>0, unless P=NP (Zuckerman, 2006 [12]).",

keywords = "Approximation algorithms, Combinatorial problems",

author = "Rapha{\"e}l Clifford and Alexandru Popa",

year = "2011",

month = mar

day = "1",

doi = "10.1016/j.ipl.2010.12.003",

language = "English",

volume = "111",

pages = "323--325",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "7",

}

TY - JOUR

T1 - Maximum subset intersection

AU - Clifford, Raphaël

AU - Popa, Alexandru

PY - 2011/3/1

Y1 - 2011/3/1

N2 - Consider the following problem. Given u sets of sets A1, ⋯,Au with elements over a universe E={e1,⋯, en}, the goal is to select exactly one set from each of A 1,⋯,Au in order to maximize the size of the intersection of the sets. In this paper we present a gap-preserving reduction from Max-Clique which enables us to show that our problem cannot be approximated within an n1-ε multiplicative factor, for any ε>0, unless P=NP (Zuckerman, 2006 [12]).

AB - Consider the following problem. Given u sets of sets A1, ⋯,Au with elements over a universe E={e1,⋯, en}, the goal is to select exactly one set from each of A 1,⋯,Au in order to maximize the size of the intersection of the sets. In this paper we present a gap-preserving reduction from Max-Clique which enables us to show that our problem cannot be approximated within an n1-ε multiplicative factor, for any ε>0, unless P=NP (Zuckerman, 2006 [12]).

KW - Approximation algorithms

KW - Combinatorial problems

UR - http://www.scopus.com/inward/record.url?scp=78650566209&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78650566209&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2010.12.003

DO - 10.1016/j.ipl.2010.12.003

M3 - Article

AN - SCOPUS:78650566209

VL - 111

SP - 323

EP - 325

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 7

ER -

Access to Document

10.1016/j.ipl.2010.12.003