*Ola Angelsmark and Johan Thapper, Linköpings Universitet*

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 *n*^{1-ε}, ε>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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.