A Microstructure Based Approach to Constraint Satisfaction Optimisation Problems

All Papers

We study two constraint satisfaction optimisation problems: The Max Value problem for CSPs, which, somewhat simplified, aims at maximising the sum of the (weighted) variable values in the solution, and the Max Ind problem, where the goal is to find a satisfiable subinstance of the original instance containing as many variables as possible. Both problems are NP-hard to approximate within n1-ε, ε>0, where n is the number of variables in the problems, which implies that it is of interest to find exact algorithms. By exploiting properties of the microstructure, we construct algorithms for solving instances of these problems with small domain sizes, and then, using a probabilistic reasoning, we show how to get algorithms for more general versions of the problems. The resulting algorithms have running times of O((0.585d)n) for Max Value (d,2)-CSP, and O((0.503d)n) for Max Ind (d,2)-CSP. Both algorithms represent the best known theoretical bounds for their respective problem, and, more importantly, the methods used are applicable to a wide range of optimisation problems.