## Abstract

Consider the following problem. Given u sets of sets A1,…,Au with elements over a universe, the goal is to select exactly one set from each of A1,…,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 n^(1−epsilon) multiplicative factor, for any epsilon >0, unless P=NP.

Translated title of the contribution | Maximum subset intersection |
---|---|

Original language | English |

Pages (from-to) | 323 - 325 |

Number of pages | 3 |

Journal | Information Processing Letters |

Volume | 111 |

DOIs | |

Publication status | Published - Mar 2011 |