Approximation algorithms for satisfiable and nearly satisfiable ordering CSPs

Yury Makarychev

We study approximation algorithms for satisfiable and nearly satisfiable instances of ordering constraint satisfaction problems (ordering CSPs). Ordering CSPs arise naturally in ra…