15.04.2005

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 fora 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 satisfythe 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 ofapproximating a tensor by the sum of a small number of"rank-1" tensors, akin to the traditional Singular ValueDecomposition (this might be of independent interest) and(2) a natural and simple way of scaling the weights. BesidesMAX-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.