View Full Document

The Approximability of Learning and Constraint Satisfaction Problems



View the full content.
View Full Document
View Full Document

2 views

Unformatted text preview:

The Approximability of Learning and Constraint Satisfaction Problems Yi Wu CMU CS 10 142 October 7 2010 School of Computer Science Carnegie Mellon University Pittsburgh PA 15213 Thesis Committee Ryan O Donnell Chair Avrim Blum Venkatesan Guruswami Subhash Khot Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy Copyright 2010 Yi Wu This research was sponsored by the National Science Foundation under grant numbers CCF 0747250 CCR0122588 US Army Research Office under grant number DAAD 190210389 and generous support from International Business Machine The views and conclusions contained in this document are those of the author and should not be interpreted as representing the official policies either expressed or implied of any sponsoring institution the U S government or any other entity Keywords Complexity Theory Approximation Algorithm Computational Learning Constraint Satisfaction Problem Hardness of Approximation Semidefinite Programming This thesis is dedicated to my parents Youqun Yu Qingchun Wu and my wife Xiaoxiao Li 4 Abstract 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 M AX C UT M AX 3 CSP M AX 2 L INR VERTEX PRICING as well as serval variants of the U NIQUE G AMES The problem of M AX C UT 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 M AX C UT problem for every optimum value of the instance we show that certain



Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view The Approximability of Learning and Constraint Satisfaction Problems and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view The Approximability of Learning and Constraint Satisfaction Problems and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?