Loading...
Please wait, while we are loading the content...
Similar Documents
Near-optimal algorithms for maximum constraint satisfaction problems (2007)
| Content Provider | CiteSeerX |
|---|---|
| Author | Charikar, Moses Makarychev, Konstantin Makarychev, Yury |
| Description | In SODA ’07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms In this paper we present approximation algorithms for the maximum constraint satisfaction problem with k variables in each constraint (MAX k-CSP). Given a (1 − ε) satisfiable 2CSP our first algorithm finds an assignment of variables satisfying a 1 − O ( √ ε) fraction of all constraints. The best previously known result, due to Zwick, was 1 − O(ε 1/3). The second algorithm finds a ck/2 k approximation for the MAX k-CSP problem (where c> 0.44 is an absolute constant). This result improves the previously best known algorithm by Hast, which had an approximation guarantee of Ω(k/(2 k log k)). Both results are optimal assuming the Unique Games Conjecture and are based on rounding natural semidefinite programming relaxations. We also believe that our algorithms and their analysis are simpler than those previously known. 1 |
| File Format | |
| Language | English |
| Publisher Date | 2007-01-01 |
| Access Restriction | Open |
| Subject Keyword | Maximum Constraint Satisfaction Problem Unique Game Conjecture Max K-csp Natural Semidefinite Programming Relaxation Second Algorithm First Algorithm Approximation Guarantee Max K-csp Problem Absolute Constant Near-optimal Algorithm Present Approximation Algorithm |
| Content Type | Text |
| Resource Type | Article |
