Stable Approximation Schemes

LUNCH:
Lunch will be served at 11:45 am.

ABSTRACT:
In a dynamic optimization problem, the goal is to maintain a solution to an optimization problem under insertions and deletions. We are interested in trade-offs between the stability of the solution and its approximation ratio. To formalize this, we introduce the concept of k-stable algorithms, which are algorithms that apply at most k changes to the solution upon each insertion and deletion. We are particularly interested in stable approximation schemes, which are update algorithms that, for any given parameter ε >0, are k(ε)-stable and maintain a solution with approximation ratio 1+ε, where the stability parameter k(ε) only depends on ε and not on the size of the current input. In this talk I will discuss stable approximation schemes (or the non-existence thereof) for three problems: the Broadcast Range-Assignment Problem, Maximum Independent Set, and Dominating Set. The talk is based on joint work with Arpan Sadhukhan and Frits Spieksma.

SPEAKER BIO:
Mark de Berg received a PhD from Utrecht University in 1992, after which he became assistant and associate professor at the same university. Currently he is a full professor at the TU Eindhoven. His main research interest is in algorithms and data structures, in particular for spatial data. He is (co-)author of two books on computational geometry and he has published over 250 peer-reviewed papers in journals and conferences. Mark is associate editor of SICOMP, Algorithmica, and JoCG and former associate editor of CGTA, IJCGA, JDA. He was an elected member of the Computational Geometry Steering Committee, the chair of the Steering Committee of the European Symposium on Algorithms, and he served on the Program Committee of over 50 international conferences.