Local search algorithms

Course code:INFOLSA
Credits:7.5 ECTS (=5.25 old credit points)
Period:periode 1 (week 36 t/m 46, dwz 2-9-2004 t/m 12-11-2004; herkansing week 52)
Timeslot:A
Participants:up till now 5 subscriptions
Schedule:Dit is een oud rooster!
formgrouptimeweekroomteacher
seminar   ma 11-1337-46 BBL-475 Hans Bodlaender
  
wo 11-1337-46 BBL-475
Contents:Many optimization problems that appear in practical settings are known to be NP-complete. Often, to solve such problems, one uses heuristical methods. One of the main types of heuristics here are the local search algorithms. In this seminal, we will study the local search algorithms for various problems, including several graph problems, scheduling problems, and other NP-hard problems.

In the seminar, we study several aspects of local search algorithms: how to design them, different types of neighborhood functions, local search algorithms with a guarantee on the quality of the solutions they give, time complexity of local search, local search metaheuristics (like simulated annealing), convergence properties, local search algorithms for specific problems.

Literature:We mainly use the following text: Wil Michiels, Emile Aarts, Jan Korst. The Foundations of Local Search. Preprint, 2004.

This book is not yet available; a prelimary printout will be handed to the participants. In addition, we may use some additional papers from the scientific literature. All literature will be handed out to the students.

Course form:We start by studying the book of Michiel, Aarts, and Korst.

Given the small number of participants, the following form of the course will be followed. If at the last moment, more participants register for the course, this form will change. The participants will together with the lecturer study the book. After the book has been studied, participants will do a small project together, where the material studied in the book is applied to a new problem.

If all students following the course speak Dutch, the language speaken in the course will be Dutch. Otherwise, the language will be English.

Presence during the meetings is obligatory.

Exam form:Quality of participation in the meetings, output, and results of final project.
Minimum effort to qualify for 2nd chance exam:Om aan de aanvullende toets te mogen meedoen is ontbreken van ten hoogte 1 toetsactiviteit toegestaan.
wijzigen?