DagSemProc.09261.4.pdf
- Filesize: 118 kB
- 3 pages
Document
A Robust PTAS for the Parallel Machine Covering Problem
Authors
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 9261
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2009-10-02
Cite As Get BibTex
Martin Skutella and Jose Verschae. A Robust PTAS for the Parallel Machine Covering Problem. In Models and Algorithms for Optimization in Logistics. Dagstuhl Seminar Proceedings, Volume 9261, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
https://doi.org/10.4230/DagSemProc.09261.4
Abstract
In general, combinatorial optimization problems are unstable: slight changes on the instance of a problem can render huge changes in the optimal solution. Thus, a natural question arises: Can we achieve stability if we only maintain approximate solutions?. In this talk I will first formalize these ideas, and then show some results on the parallel machine covering problem. In particular I will derive a robust PTAS, i.e., I will show how to construct a solution that is not only $(1-epsilon)$-approximate, but is also stable. That is, if the instance is changed by adding or removing a job, then we can construct a new near-optimal solution by only slightly modifying the previous one.
Subject Classification
Keywords
- Stability
- approximation schemes
- online algorithms
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads