The theory of NP-hardness of approximation has led to numerous tight characterizations of approximability of hard combinatorial optimization problems. Nonetheless, there are many fundamental problems which are out of reach for these techniques, such as problems that can be solved (or approximated) in quasi-polynomial time, parameterized problems and problems in P.
This dissertation continues the line of work that develops techniques to show inapproximability results for these problems. In the process, we provide hardness of approximation results for the following problems. - Problems Between P and NP: Dense Constraint Satisfaction Problems (CSPs), Densest k-Subgraph with Perfect Completeness, VC Dimension, and Littlestone's Dimension. - Parameterized Problems: k-Dominating Set, k-Clique, k-Biclique, Densest k-Subgraph, Parameterized 2-CSPs, Directed Steiner Network, k-Even Set, and k-Shortest Vector. - Problems in P: Closest Pair, and Maximum Inner Product.
Some of our results, such as those for Densest k-Subgraph, Directed Steiner Network and Parameterized 2-CSP, also present the best known inapproximability factors for the problems, even in the (believed) NP-hard regime. Furthermore, our results for k-Dominating Set and k-Even Set resolve two long-standing open questions in the field of parameterized complexity.
Title
Approximation and Hardness: Beyond P and NP
Published
2019-05-16
Full Collection Name
Electrical Engineering & Computer Sciences Technical Reports
Other Identifiers
EECS-2019-49
Type
Text
Extent
278 p
Archive
The Engineering Library
Usage Statement
Researchers may make free and open use of the UC Berkeley Library’s digitized public domain materials. However, some materials in our online collections may be protected by U.S. copyright law (Title 17, U.S.C.). Use or reproduction of materials protected by copyright beyond that allowed by fair use (Title 17, U.S.C. § 107) requires permission from the copyright owners. The use or reproduction of some materials may also be restricted by terms of University of California gift or purchase agreements, privacy and publicity rights, or trademark law. Responsibility for determining rights status and permissibility of any use or reproduction rests exclusively with the researcher. To learn more or make inquiries, please see our permissions policies (https://www.lib.berkeley.edu/about/permissions-policies).
