Ph D abstract - Ola Angelsmark
Constructing Algorithms for Constraint Satisfaction and Related
- Methods and Applications
Akademisk avhandling som för avläggande av teknologie
Linköpings universitet kommer att offentligt försvaras i
B, Linköpings universitet, fredagen den 3 juni 2005, kl 13.15.
In this thesis, we will discuss the construction of algorithms for
solving Constraint Satisfaction Problems (CSPs), and describe two new
ways of approaching them. Both approaches are based on the idea that it
is sometimes faster to solve a large number of restricted problems than
a single, large, problem. One of the strong points of these methods is
that the intuition behind them is fairly simple, which is a definite
advantage over many techniques currently in use.
The first method, the covering method, can be described as follows: We
want to solve a CSP with n variables, each having a domain with d
elements. We have access to an algorithm which solves problems where
domain has size e<d, and we want to cover the original problem using
number of restricted instances, in such a way that the solution set is
preserved. There are two ways of doing this, depending on the amount of
work we are willing to invest; either we construct an explicit covering
and end up with a deterministic algorithm for the problem, or we use a
probabilistic reasoning and end up with a probabilistic algorithm.
The second method, called the partitioning method, relaxes the demand
the underlying algorithm. Instead of having a single algorithm for
solving problems with domain less than d, we allow an arbitrary number
of them, each solving the problem for a different domain size. Thus by
splitting, or partitioning, the domain of the large problem, we again
solve a large number of smaller problems before arriving at a solution.
Armed with these new techniques, we study a number of different
problems; the decision problems (d,l)-CSP and k-COLOURABILITY, together
with their counting counterparts, as well as the optimisation problems
MAX IND CSP, MAX VALUE CSP, MAX CSP, and MAX HAMMING CSP. Among the
results, we find a very fast, polynomial space algorithm for
k-colourability of graphs.
This work has been supported by the National Graduate School in
Science (CUGS), and by the Swedish Research Council (VR) under grant