Skip to content. Skip to navigation
McGill Home SOCS Home
Personal tools
You are here: Home Announcements and Events Seminars profile

Seminars
Fall 2014 Schedule
Winter 2015 Schedule
Archive


         
     
 
2013/07/24, MC103, 12 - 12:30

Hardness of Approximation: Nearly Linear-Size PCP and The Limits of Time-Approximability Trade-off
Bundit Laekhanukit , PhD student, SOCS

Area: theory

Abstract:

The theory of NP-completeness is a fundamental theory in computer science, which separates problems into "easy" and "hard" problems. While many problems we encounter are "hard" (i.e., no polynomial-time algorithm exists unless P=NP), this does not rule out the possibility of getting an approximate solution. Unfortunately, even finding an approximate solution has its limit.

In this talk, we will discuss the limits of approximations of the maximum independent set problem (Independent Set) and the k-hypergraph pricing problem (Pricing). Under the assumption that SAT does not has a sub-exponential-time algorithm, we will show that no algorithm with a running time of 2^{n/r} could give an r-approximate solution for Independent Set; this is a tight hardness result. For the case of Pricing, we will show a sharp contrast in the approximability of the quasi-polynomial-time and polynomial-time algorithms.