Approximating Bounded Occurrence Ordering CSPs

DOI10.1007/978-3-642-32512-0_14MaRDI QIDQ3167393zbMATH OpenOpenAlexFDO

Authors Yuan Zhou, Venkatesan Guruswami

Publication date 2 November 2012

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-32512-0_14

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25)

Recommendations

• On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems
• On the NP-hardness of approximating ordering-constraint satisfaction problems
• Approximation Algorithms for CSPs
• On bounded occurrence constraint satisfaction
• Beating the random ordering is hard: every ordering CSP is approximation resistant
• Streaming approximation resistance of every ordering CSP
• Local search is better than random assignment for bounded occurrence ordering k-CSPs
• The complexity of approximating bounded-degree Boolean \#CSP

Cited in

(8)

• On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems
• Improved parameterized algorithms for above average constraint satisfaction
• On the NP-hardness of approximating ordering-constraint satisfaction problems
• Local search is better than random assignment for bounded occurrence ordering k-CSPs
• Beating the random ordering is hard: every ordering CSP is approximation resistant
• Streaming approximation resistance of every ordering CSP
• Streaming approximation resistance of every ordering CSP
• Finding an optimal alphabet ordering for Lyndon factorization is hard

This page was built for publication: Approximating Bounded Occurrence Ordering CSPs

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