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

Fall 2015 Schedule
Winter 2016 Schedule

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


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.