On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems

DOI10.1007/978-3-642-40328-6_3zbMath1334.68083arXiv1307.5090OpenAlexW3023311638MaRDI QIDQ2851846

Rajsekar Manokaran, Cenny Wenner, Per Austrin

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)

Related Items (3)

An Exact Method for the Minimum Feedback Arc Set Problem ⋮ On the maximum acyclic subgraph problem under disjunctive constraints ⋮ Cable tree wiring -- benchmarking solvers on a real-world scheduling problem with a variety of precedence constraints

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