Analysis of approximation algorithms for maximal temporal constraint satisfaction problems

This paper presents an experimental study of the different local search techniques to solve Maximal Temporal Constraint Satisfaction Problems. Comparisons were carried out using Min-Conflicts-Random-Walk, Steepest-Descent-Random-Walk and Tabu Search methods. Empirical evidence shows that the Min-Conflicts-Random-Walk method finds almost always solutions of better quality, i.e solutions having smaller number of violated constraints and is faster than the other approximation methods to find solutions of the same quality.