Theory Lunch Seminar: Talk One
— 12:30pm
Location:
ASA Conference Room 6115
-
Gates & Hillman Centers
Speaker:
EUIWOONG LEE
,
Ph.D. Student
http://www.cs.cmu.edu/~euiwoonl/
The Unique Coverage problem, given a universe V of elements and a collection E of subsets of V, asks to find $S \subseteq V$ to maximize the number of e in E that intersects S in exactly one element. When each e has cardinality at most k, it is also known as 1-in-k Hitting Set, and admits a simple Omega(1 / log k)-approximation algorithm. For constant k, we prove that 1-in-k Hitting Set is NP-hard to approximate within a factor O(1 / log k). This improves the result of Guruswami and Zhou [SODA'11, ToC'12], who proved the same result assuming the Unique Games Conjecture. For Unique Coverage, we prove that it is hard to approximate within a factor O(1 / log^{1 - epsilon} n) for any epsilon > 0, unless NP admits quasipolynomial time algorithms. This improves the results of Demaine et al. [SODA'06, SICOMP'08], including their O(1 / log^{1/3} n) inapproximability factor which was proven under the Random 3SAT Hypothesis. Our simple proof combines ideas from two classical inapproximability results for Set Cover and Constraint Satisfaction Problem, made efficient by various derandomization methods based on bounded independence. Based on joint work with Venkatesan Guruswami. — Euiwoong Lee is a PhD student at Carnegie Mellon University, advised by Venkat Guruswami. Before coming to CMU, he obtained B.S. and M.S. from Caltech. His research interests include approximation algorithms and hardness of approximation for optimization problems. Talks from SODA 2016
Event Website:
http://www.cs.cmu.edu/~theorylunch/20160120.html