The Approximability of Learning and Constraint Satisfaction Problems
Abstract
An alpha- approximation algorithm is an algorithm guaranteed to output a solution that is within an alpha ratio of the optimal solution. We are interested in the following question: Given an NP-hard optimization problem, what is the best approximation guarantee that any polynomial time algorithm could achieve? We mostly focus on studying the approximability of two classes of NP-hard problems: Constraint Satisfaction Problems (CSPs) and Computational Learning Problems. For CSPs, we mainly study the approximability of MAX CUT, MAX 3-CSP MAX 2-LINR, VERTEX-PRICING, as well as serval variants of the UNIQUEGAMES. The problem of MAX CUT is to find a partition of a graph so as to maximize the number of edges between the two partitions. Assuming the Unique Games Conjecture, we give a complete characterization of the approximation curve of the MAX CUT problem: for every optimum value of the instance, we show that certain SDP algorithm with RPR2 rounding always achieve the optimal approximation curve. The input to a 3-CSP is a set of Boolean constraints such that each constraint contains at most 3 Boolean variables. The goal is to find an assignment to these variables to maximize the number of satisfied constraints. We are interested in the case when a 3-CSP is satisfiable, i.e. there does exist an assignment that satisfies every constraint. Assuming the d-to-1 conjecture (a variant of the Unique Games Conjecture), we prove that it is NP-hard to give a better than 5/8-approximation for the problem. Such a result matches a SDP algorithm by Zwick which gives a 5/8-approximation problem for satisfiable 3-CSP. In addition, our result also conditionally resolves a fundamental open problem in PCP theory on the optimal soundness for a 3-query nonadaptive PCP system for NP with perfect completeness. The problem of MAX 2-LINZ involves a linear systems of integer equation these equations are so simple such that each equation contains at most 2 variables.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 07, 2010
- Accession Number
- ADA532824
Entities
People
- Yi Wu
Organizations
- Carnegie Mellon University