Robust PTAS for Machine Covering and Packing
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.