[Dept. of Computer Science]

Experimentation Project ACS


Title Local Search on Networks
Student Maarten Niederer
Supervisor Hans Bodlaender
ECTS 7.5
Related Course(s) Algorithms and Networks
Description In this project, a number of local search methods are compared on two well-known network problems:
  • the dominating set problem, and
  • the feedback vertex set problem.
Given a problem and an instance, let S denote the solution space, and let denote the set of optima.
Furthermore, let denote the solutions with quality (1+e) * optimum.
Finally, let , where denotes the local optimum found by algorithm a, when s is used as a starting value.
The problem now is to find a good guideline for constructing hill-climbing algorithms.
The quality of the hill-climbing algorithms is determined by the sizes of the spaces ,
or alternatively, by the probabilities .