Local Search Is Better Than Random Assignment for Bounded Occurrence Ordering K-CSPs
The authors prove that the Bounded Occurrence Ordering k-CSP Problem is not approximation resistant. They give a very simple local search algorithm that always performs better than the random assignment algorithm (unless, the number of satisfied constraints does not depend on the ordering). In this paper, they give a very simple local search algorithm for ordering constraints satisfaction problems that works better than the random assignment for those instances of the ordering k-CSP problem, where each variable is used only a bounded number of times. To motivate the study of the problem, they first overview known results for regular constraint satisfaction problems.