On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems

DOI10.1007/978-3-642-40328-6_3MaRDI QIDQ2851846zbMATH OpenOpenAlexFDO

Authors Per Austrin, Rajsekar Manokaran, Cenny Wenner

Publication date 4 October 2013

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

Full work available at URL https://arxiv.org/abs/1307.5090

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: We show improved NP-hardness of approximating Ordering Constraint Satisfaction Problems (OCSPs). For the two most well-studied OCSPs, Maximum Acyclic Subgraph and Maximum Betweenness, we prove inapproximability of $14/15+epsilon$ and $1/2+epsilon$. An OCSP is said to be approximation resistant if it is hard to approximate better than taking a uniformly random ordering. We prove that the Maximum Non-Betweenness Problem is approximation resistant and that there are width-$m$ approximation-resistant OCSPs accepting only a fraction $1/(m/2)!$ of assignments. These results provide the first examples of approximation-resistant OCSPs subject only to P $eq$ NP.

Recommendations

• On the NP-hardness of approximating ordering-constraint satisfaction problems
• On the hardness of approximating some NP-optimization problems related to minimum linear ordering problem
• scientific article; zbMATH DE number 1759471
• The approximability of constraint satisfaction problems
• On the Complexity of Some Ordering Problems
• On approximability of linear ordering and related NP-optimization problems on graphs (extended abstract)
• Approximating Bounded Occurrence Ordering CSPs
• On the efficient approximability of constraint satisfaction problems
• A non-binary constraint ordering heuristic for constraint satisfaction problems
• On approximability of linear ordering and related NP-optimization problems on graphs.

Cited in

(9)

• Cable tree wiring -- benchmarking solvers on a real-world scheduling problem with a variety of precedence constraints
• On the NP-hardness of approximating ordering-constraint satisfaction problems
• Beating the random ordering is hard: every ordering CSP is approximation resistant
• Approximating Bounded Occurrence Ordering CSPs
• On the maximum acyclic subgraph problem under disjunctive constraints
• An exact method for the minimum feedback arc set problem
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• Streaming approximation resistance of every ordering CSP
• Streaming approximation resistance of every ordering CSP

This page was built for publication: On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems

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