Carnegie Mellon University
Browse
The Approximability of Learning and Constraint Satisfaction Probl.pdf (1.54 MB)
Download file

The Approximability of Learning and Constraint Satisfaction Problems

Download (1.54 MB)
thesis
posted on 2010-10-07, 00:00 authored by Yi Wu

An α-approximation algorithm is an algorithm guaranteed to output a solution
that is within an α 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 equations;
these equations are so simple such that each equation contains at
most 2 variables. The goal is to find an assignment to the variables so as
to maximize the total number of satisfied equations. It is a natural generalization
of the Unique Games Conjecture which address the hardness of
the same equation systems over finite fields. We show that assuming the
Unique Games Conjecture, for a MAX 2-LINZ instance, even that there
exists a solution that satisfies 1−ε of the equations, it is NP-hard to find
one that satisfies ² of the equations for any ε > 0.

History

Date

2010-10-07

Degree Type

  • Dissertation

Department

  • Computer Science

Degree Name

  • Doctor of Philosophy (PhD)

Advisor(s)

Ryan O'Donnell,Avrim Blum,Venkatesan Guruswami,Subhosh Khot