Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2005 Copyright 2005 Universität Bonn, Institut für Informatik, Abt. V
85266

15.04.2005

Tensor Decomposition and Approximation Schemes for Constraint Satisfaction Problems
Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski and Santosh Vempala
[Download PostScript] [Download PDF]

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.

Last Change: 11/05/14 at 10:32:49
 English
Universität Bonn -> Institut für Informatik -> Abteilung V