Schlüsselwörter
(Englisch)
|
optimization; reoptimization; algorithms; complexity
|
Forschungsprogramme
(Englisch)
|
COST-Action 293 - Graphs and algorithms in communication networks
|
Kurzbeschreibung
(Englisch)
|
Given a discrete optimization problem instance with an optimal (or approximate) solution, and a variation of the problem instance that we obtain through small, local modifications, what can we learn about the new solution? Does the old solution help at all? Under what circumstances does it help? How much does it help? How much does it help for the runtime, how much for the quality of the output?
|
Weitere Hinweise und Angaben
(Englisch)
|
Full name of research-institution/enterprise: ETH Zürich Institut für Theoretische Informatik ETH-Zentrum CAB H 19.1
|
Partner und Internationale Organisationen
(Englisch)
|
BE, CH, DE, DK, ES, FR, GR, HR, HU, IL, IT, NL, NO, PL, SE, SI, SK, UK
|
Abstract
(Englisch)
|
The classical optimization theory focuses on finding a good quality solution for an instance of a problem, where very little is known about the instance. In reality however, we sometimes have considerable knowledge about the problem instance. For example a problem instance can arise from a small modification of a previous problem instance. Thus, there might be a need to compute a solution, given some prior knowledge of a solution for a similar instance. As an example, imagine that an optimal timetable (for some objective function, under some constraints) for a given railway network is known, and that now a railway station is closed down. It is intuitively obvious that we should profit somehow from the old timetable when we try to find a new timetable. These considerations lead to the concept of reoptimization. Reoptimization benefits from an old optimal solution (or its good approximation) when solving a modified instance. We believe that reoptimization leads to a better understanding of optimization problems and the nature of their complexity. Our initial results show that NP-hard problems vary from the reoptimization point of view. Some are easier to reoptimize than others, and for some the prior knowledge does not help at all. In principle however, a reoptimization version of a problem remains NP-hard, although may become easier to approximate. This motivates investigating reoptimization as a useful classification tool for NP-hard problems.
|
Datenbankreferenzen
(Englisch)
|
Swiss Database: COST-DB of the State Secretariat for Education and Research Hallwylstrasse 4 CH-3003 Berne, Switzerland Tel. +41 31 322 74 82 Swiss Project-Number: C06.0108
|
