AG 1, AG 4, RG1, MMCI, AG 3, AG 5, SWS   Info

AG Audience

English

30 Minutes

Saarbrücken

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 explain some models that try to 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.

This is joint work with Martin Skutella.

Nicole Megow

--email hidden

passcode not visible

logged in users only