Approximation algorithms for satisfiable and nearly satisfiable ordering CSPs
This work addresses the poorly understood approximability of ordering CSPs, which are critical in practical applications like ranking and scheduling, but it is incremental as it builds on existing CSP frameworks.
The authors tackled the problem of approximating satisfiable and nearly satisfiable ordering constraint satisfaction problems (CSPs), which are important in ranking and scheduling, by introducing a general algorithmic framework that reduces the search to an optimization problem over randomized transformations, and they showed that this framework can compute near-optimal guarantees efficiently for any finite ordering constraint language.
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. 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.