Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.09261.4
URN: urn:nbn:de:0030-drops-21609
URL: https://drops.dagstuhl.de/opus/volltexte/2009/2160/
Skutella, Martin ; Verschae, Jose
A Robust PTAS for the Parallel Machine Covering Problem
| pdf-format: |
|
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.
BibTeX - Entry
@InProceedings{skutella_et_al:DagSemProc.09261.4,
author = {Skutella, Martin and Verschae, Jose},
title = {{A Robust PTAS for the Parallel Machine Covering Problem}},
booktitle = {Models and Algorithms for Optimization in Logistics},
pages = {1--3},
series = {Dagstuhl Seminar Proceedings (DagSemProc)},
ISSN = {1862-4405},
year = {2009},
volume = {9261},
editor = {Cynthia Barnhart and Uwe Clausen and Ulrich Lauther and Rolf H. M\"{o}hring},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2009/2160},
URN = {urn:nbn:de:0030-drops-21609},
doi = {10.4230/DagSemProc.09261.4},
annote = {Keywords: Stability, approximation schemes, online algorithms}
}
| Keywords: | Stability, approximation schemes, online algorithms | |
| Seminar: | 09261 - Models and Algorithms for Optimization in Logistics | |
| Issue date: | 2009 | |
| Date of publication: | 02.10.2009 |
