Talks
Fall 2015

Parameterized Inapproximability of Max k-Subset Intersection under ETH
Tuesday, November 3rd, 2015, 11:30 am–12:00 pm
Speaker:
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.
Attachment | Size |
---|---|
![]() | 311.78 KB |