Accession Number:

ADA532824

Title:

The Approximability of Learning and Constraint Satisfaction Problems

Descriptive Note:

Master's thesis

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

2010-10-07

Pagination or Media Count:

240.0

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 58-approximation for the problem. Such a result matches a SDP algorithm by Zwick which gives a 58-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.

Subject Categories:

  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE