Not all hardness of approximation needs the PCP Theorem
Almost all the best hardness-of-approximation results we know require at least the PCP Theorem. But not all do... Here are three examples:
1. Minimum Metric k-Center: In this problem you are given an undirected graph with distances satisfying the triangle inequality. You are also given an integer k. Your task is to pick k "centers" (vertices in the graph) with the goal of minimizing the maximum distance of any vertex to a center.
As early as 1979, Hsu & Nemhauser showed by a simple NP-completeness reduction that it's hard to tell the difference between instances with value 1 and instances with value 2 (even in graphs where all edges have distances 1 and 2). This was also shown by Plesník in 1980. This immediately implies there is no (2-eps)-approximation algorithm. On the other hand, there is also an easy 2-approximation, first given by Gonzalez in 1985. This gives a sharp hardness-of-approximation result, as noted in 1985 (seven years before the PCP Theorem!) by Hochbaum & Shmoys.
2. In 1993, right after the PCP Theorem had come out, Håstad, Philips, and Safra considered the problem of satisfiability of multilinear degree two equations over GF[p]. (We tangentially touched on his problem, with p = 2, in the construction of Assignment Testers.) In the paper the authors give an easy (1/p - 1/p^2)-approximation algorithm. They also use a cute argument based on epsilon-biased spaces (which we will see on Monday for SET-COVER; I think the argument can also be based on error-correcting codes) to show that it is NP-hard to give a (1/p + eps)-approximation for any eps > 0 (even polynomially small). The main reason why HPS are able to give this essentially-sharp result is that the quadratic equations don't have to be "local", as they do in PCP-type constructions; they many depend on many variables.
3. Since 3-colorability is NP-hard, we know that it is hard to distinguish graphs with chromatic number 3 from graphs with chromatic number 4. Khanna, Linial, and Safra improved on this in 1993, giving an intricate PCP-based proof that it is hard to distinguish chromatic number 3 from chromatic number 5. This is the strongest result we know about coloring 3-colorable graphs. However, it turns out that KLS's use of the PCP Theorem was unnecessary; in 2000, Khanna and Guruswami gave a new proof of the same result using nothing but a classical NP-completeness reduction from Independent-Set.
1. Minimum Metric k-Center: In this problem you are given an undirected graph with distances satisfying the triangle inequality. You are also given an integer k. Your task is to pick k "centers" (vertices in the graph) with the goal of minimizing the maximum distance of any vertex to a center.
As early as 1979, Hsu & Nemhauser showed by a simple NP-completeness reduction that it's hard to tell the difference between instances with value 1 and instances with value 2 (even in graphs where all edges have distances 1 and 2). This was also shown by Plesník in 1980. This immediately implies there is no (2-eps)-approximation algorithm. On the other hand, there is also an easy 2-approximation, first given by Gonzalez in 1985. This gives a sharp hardness-of-approximation result, as noted in 1985 (seven years before the PCP Theorem!) by Hochbaum & Shmoys.
2. In 1993, right after the PCP Theorem had come out, Håstad, Philips, and Safra considered the problem of satisfiability of multilinear degree two equations over GF[p]. (We tangentially touched on his problem, with p = 2, in the construction of Assignment Testers.) In the paper the authors give an easy (1/p - 1/p^2)-approximation algorithm. They also use a cute argument based on epsilon-biased spaces (which we will see on Monday for SET-COVER; I think the argument can also be based on error-correcting codes) to show that it is NP-hard to give a (1/p + eps)-approximation for any eps > 0 (even polynomially small). The main reason why HPS are able to give this essentially-sharp result is that the quadratic equations don't have to be "local", as they do in PCP-type constructions; they many depend on many variables.
3. Since 3-colorability is NP-hard, we know that it is hard to distinguish graphs with chromatic number 3 from graphs with chromatic number 4. Khanna, Linial, and Safra improved on this in 1993, giving an intricate PCP-based proof that it is hard to distinguish chromatic number 3 from chromatic number 5. This is the strongest result we know about coloring 3-colorable graphs. However, it turns out that KLS's use of the PCP Theorem was unnecessary; in 2000, Khanna and Guruswami gave a new proof of the same result using nothing but a classical NP-completeness reduction from Independent-Set.
posted by Ryan O'Donnell at 1:38 PM
3 Comments:
There is also an easy proof that travelling salesman is not approximable by any polynomial factor, via reduction to the Hamiltonian cycle problem; see Papadimitriou's book.
Right, in the non-metric case.
I love the Metric TSP approximation problem -- nobody can touch the 3/2 factor Christofides gave in a 1976 CMU technical report.
Christofides's most recent paper? "The Design of Corporate Tax Structures".
I'd add one more example concerning coloring.
It is NP-hard to tell if a graph is 3-colorable. This implies that a better than 4/3 approximation for coloring is NP-hard (this can be shown also for 4/3-approximation in an "asymptotic sense", i.e., the number of colors we use should be at most 4/3 OPT + some absolute constant). Garey and Johnson, in a 1976 JACM paper "The complexity of near-optimal graph coloring", showed NP-hardness of approximating within any factor less than 2 (the proof is clever but only about a page in length). However, no stronger inapproximability factor was shown till the PCP machinery was discovered.
Note that for Clique, by self-improvement using graph products (your homework problem!), factor 1.01 hardness implies hardness within *any* constant factor. For coloring no such self-improvement is known.
-- Venkat
Post a Comment
<< Home