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.
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 . |