2009/01/01 by Martin Skutella, Skutella, Martin, José Verschae +1
Computer Science · Engineering · #Optimization and Packing Problems #Scheduling and Optimization Algorithms #Stability #approximation schemes #online algorithms #semigroups and automata theory
paper · doi:10.4230/dagsemproc.09261.4
openalex publication_date 2009/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.