Talks
Fall 2015

Parameterized Inapproximability of Max k-Subset Intersection under ETH

Tuesday, November 3rd, 2015, 11:30 am12:00 pm

Add to Calendar

Given a collection of n subsets over a finite set of elements {1,2,…, m}, the goal of Maximum k Subset Intersection problem is to select k subsets whose intersection has maximum cardinality.  In this talk, we show that, under ETH, this problem has no f(k)n^{o{\sqrt{k}}}-time approximation algorithm within ratio n^{o(1/\sqrt{k})} for any computable function f.