Tensor decomposition and approximation schemes for constraint satisfaction problems

Abstract

The only general class of MAX-rCSP problems for which Polynomial Time Approximation Schemes (PTAS) are known are the dense problems. In this paper, we give PTAS's for a much larger class of weighted MAX-rCSP problems which includes as special cases the dense problems and, for r = 2, all metric instances (where the weights satisfy the triangle inequality) and quasimetric instances; for r > 2, our class includes a generalization of metrics. Our algorithms are based on low-rank approximations with two novel features: (1) a method of approximating a tensor by the sum of a small number of "rank-1" tensors, akin to the traditional Singular Value Decomposition (this might be of independent interest) and (2) a simple way of scaling the weights. Besides MAX-rCSP problems, we also give PTAS's for problems with a constant number of global constraints such as maximum weighted graph bisection and some generalizations.