PTAS for Sparse General-valued CSPs
From MaRDI portal
Publication:6075749
DOI10.1145/3569956arXiv2012.12607OpenAlexW3114199807MaRDI QIDQ6075749
Stanislav Živný, Balázs F. Mezei, Marcin Wrochna
Publication date: 23 October 2023
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2012.12607
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Hard constraint satisfaction problems have hard gaps at location 1
- Sublinear separators, fragility and subexponential expansion
- Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
- A partial k-arboretum of graphs with bounded treewidth
- Gibbs measures and dismantlable graphs
- Excluding any graph as a minor allows a low tree-width 2-coloring
- On fractional fragility rates of graph classes
- Dismantlability, connectedness, and mixing in relational structures
- A dichotomy for minimum cost graph homomorphisms
- Algorithms for graphs embeddable with few crossings per edge
- Local tree-width, excluded minors, and approximation algorithms
- The Approximability of Constraint Satisfaction Problems
- Approximation of Minimum Cost Homomorphisms
- A Dichotomy Theorem for the General Minimum Cost Homomorphism Problem
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Algebraic Properties of Valued Constraint Satisfaction Problem
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- On the power of unique 2-prover 1-round games
- MAX ONES Generalized to Larger Domains
- Approximation algorithms for NP-complete problems on planar graphs
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- The Dichotomy of Minimum Cost Homomorphism Problems for Digraphs
- Hybrid Tractable Classes of Constraint Problems
- Approximation Algorithms for CSPs
- The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side
- Baker game and polynomial-time approximation schemes
- When is the evaluation of conjunctive queries tractable?
- The Complexity of Boolean Surjective General-Valued CSPs
- A linear time algorithm for finding tree-decompositions of small treewidth
- The Complexity of General-Valued CSPs
- Dualities for Constraint Satisfaction Problems
- Introduction to the Maximum Solution Problem
This page was built for publication: PTAS for Sparse General-valued CSPs
