Approximation Algorithms for Satisfiable and Nearly Satisfiable Ordering CSPs

We study approximation algorithms for satisfiable and nearly satisfiable instances of ordering constraint satisfaction problems (ordering CSPs). Ordering CSPs arise naturally in ranking and scheduling, yet their approximability remains poorly understood beyond a few isolated cases. Apart from tractable cases in which satisfiable instances can be solved exactly in polynomial time, prior nontrivial guarantees in the satisfiable regime were known only for Betweenness, while prior algorithms in the nearly satisfiable regime applied only to bounded-arity precedence CSPs – CSPs whose constraints are conjunctions of clauses of the form xi < xj. We introduce a general framework for designing approximation algorithms for ordering CSPs. The framework relaxes an input instance to an auxiliary ordering CSP, solves the relaxation, and then applies a randomized transformation to obtain an ordering for the original instance. This reduces the search for approximation algorithms to an optimization problem over randomized transformations. Our main technical contribution is to show that the power of this framework is captured by a structured class of transformations, which we call strong IDU transformations: every transformation used in the framework can be replaced by a strong IDU transformation without weakening the resulting approximation guarantee. We then classify strong IDU transformations and show that optimizing over them reduces to an explicit optimization problem whose dimension depends only on the maximum predicate arity k and the desired precision δ > 0. As a consequence, for any finite ordering constraint language, we can compute a strong IDU transformation whose guarantee is within δ of the best guarantee achievable by the framework, in time depending only on k and δ. The framework applies broadly and yields nontrivial approximation guarantees for a wide class of ordering predicates; the following arity-4 results illustrate its scope. Among NP-hard ordering CSPs defined by a single predicate of arity 4, we show that at least 15051 CSPs admit nontrivial approximation in the satisfiable regime. Moreover, among NP-hard and polynomial-time solvable single-predicate ordering CSPs of arity 4 – excluding bounded-arity precedence CSPs – at least 843 predicates admit nontrivial approximation in the nearly satisfiable regime. Specifically, given a (1−ε)-satisfiable instance, our algorithm produces an ordering that satisfies at least an α − O(ε logn loglogn) fraction of the constraints, where α > αrandom depends only on the predicate.