Tensor decomposition and approximation schemes for constraint satisfaction problems
Tensor decomposition and approximation schemes for constraint satisfaction problems
复制标题
DOI：
10.1145/1060590.1060701
复制
发表时间：
2005-05
期刊：
影响因子：
--
通讯作者：
W. F. D. L. Vega;Marek Karpinski;R. Kannan;S. Vempala
中科院分区：
文献类型：
--
作者：
W. F. D. L. Vega;Marek Karpinski;R. Kannan;S. Vempala
已知多项式时间近似方案（PTAS）的MAX-rCSP问题的唯一一般类是稠密问题。在本文中，我们给PTAS的一个更大的类加权MAX-rCSP问题，其中包括作为特殊情况下的稠密问题，并为r = 2，所有的度量实例（其中的权重满足三角不等式）和拟度量的情况下，r > 2，我们的类包括一个推广的度量。我们的算法基于具有两个新特征的低秩近似：（1）通过少量“秩-1”张量的和来近似张量的方法，类似于传统的奇异值分解（这可能是独立的兴趣）和（2）缩放权重的简单方法。除了MAX-rCSP问题，我们还给出了PTAS的问题与一个常数的全球性的限制，如最大加权图平分和一些推广。
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.