Campus Event Calendar

Event Entry

New for: D3

What and Who

A Robust PTAS for Machine Covering and Packing

Jose Verschae
TU Berlin
AG 1, AG 4, RG1, MMCI, AG 3, AG 5, SWS  
AG Audience

Date, Time and Location

Monday, 26 April 2010
30 Minutes
E1 4


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

Nicole Megow, 04/20/2010 09:33 -- Created document.