pdf icon
Volume 10 (2014) Article 13 pp. 341-358
APPROX-RANDOM 2012 Special Issue
Approximation Algorithm for Non-Boolean Max-$k$-CSP
Received: October 31, 2012
Revised: May 12, 2014
Published: October 10, 2014
Download article from ToC site:
[PDF (282K)] [PS (1083K)] [Source ZIP]
Misc.:
[About the Authors] [HTML Bibliography] [BibTeX]
Keywords: approximation algorithms, semidefinite programming, constraint satisfaction
Categories: algorithms, approximation algorithms, semidefinite programming, constraint satisfaction, special issue, APPROX, APPROX-RANDOM 2012 special issue
ACM Classification: F.2.2, G.1.6
AMS Classification: 68W25

Abstract: [Plain Text Version]

In this paper we present a randomized polynomial-time approximation algorithm for Max-$k$-CSPd. In Max-$k$-CSPd we are given a set of predicates of arity $k$ over an alphabet of size $d$. Our goal is to find an assignment that maximizes the number of satisfied constraints.

Our algorithm has approximation factor $\Omega(kd/d^k)$ (when $k \geq \Omega(\log d)$). The best previously known algorithm has approximation factor $\Omega({k\log d}/{d^k})$. Our bound is asymptotically optimal when $d = \Omega(d)$.

We also give an approximation algorithm for the Boolean Max-$k$-CSP2 problem with a slightly improved approximation guarantee.