Tensor decomposition and approximation schemes for constraint satisfaction problems

DOI10.1145/1060590.1060701MaRDI QIDQ3581412zbMATH OpenOpenAlexFDO

Authors W. Fernandez de la Vega, R. Kannan, Marek Karpinski, Santosh S. Vempala

Publication date 16 August 2010

Published in Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1060590.1060701

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Recommendations

• Polynomial time approximation schemes for dense instances of minimum constraint satisfaction
• scientific article; zbMATH DE number 1303558
• The approximability of constraint satisfaction problems
• Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems
• Sub-exponential approximation schemes for CSPs: from dense to almost sparse

Cited in

(11)

• Numerical multilinear algebra and its applications
• Hardness of fully dense problems
• scientific article; zbMATH DE number 6096665 (Why is no real title available?)
• Optimal cuts and partitions in tree metrics in polynomial time
• Tensor sparsification via a bound on the spectral norm of random tensors: Algorithm 1.
• A Flexible and Efficient Algorithmic Framework for Constrained Matrix and Tensor Factorization
• Approximate real symmetric tensor rank
• Randomized interpolative decomposition of separated representations
• Min-CSPs on complete instances. II: Polylogarithmic approximation for Min-NAE-3-SAT
• A randomized algorithm for a tensor-based generalization of the singular value decomposition
• Compact orbit spaces in Hilbert spaces and limits of edge-colouring models

This page was built for publication: Tensor decomposition and approximation schemes for constraint satisfaction problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3581412)