Smoothed performance guarantees for local jumps in makespan scheduling
We consider performance guarantees of local optima w.r.t. the jump neighborhood for makespan scheduling. Although local search methods exhibit good empirical behavior, they often have a bad worst case performance. In this talk, we consider smoothed performance guarantees on the quality of local optima, trying to explain their empirical behavior. Smoothed analysis was introduced by Spielman and Teng (JACM 2004) as a hybrid between worst case and average case analysis, to explain the good behavior of algorithms that have a bad worst case performance. Up to now, smoothed analysis has been mainly applied to the running time of algorithms. We will use smoothed analysis to investigate the approximation ratio of an algorithm, that is, the ratio between the value of an approximate solution and the optimal solution value. In the last decade, there has been a strong interest in understanding the worst case behavior of local optimal solutions. We extend this research by investigating whether or not this worst case behavior is robust. We will apply the concept of smoothed performance guarantees to several local optima for makespan scheduling problems. As a by-product, we also get a smoothed price of anarchy for the corresponding scheduling games.
This talk is based on joint work with: Tobias Brunsch, Heiko Röglin, and Cyriel Rutten
About Tjark Vredeveld:
Tjark Vredeveld is an associate professor in Mathematics of Operations Research at Maastricht University School of Business and Economics. He obtained a MSc in Econometrics and Operations Research from the Erasmus University in Rotterdam, the Netherlands and his PhD in Mathematics from Eindhoven University of Technology. After receiving his PhD, he went for a 5 month postdoc to La Sapienza University in Rome, Italy, where he worked at the Dipertimento di Informatica e Sistemistica. In November 2002, he moved to Berlin, Germany, where he was a postdoc at the Zuse Institute Berlin. In January 2005, he started as an assistant professor at Maastricht University, where he now is associate professor. His research interests lie in the field of online and approximation algorithms, mainly for scheduling problems and especially for stochastic scheduling problems. Tjark Vredeveld has supervised 6 PhD students and numerous BSc and MSc students and is coordinator of an EU FP7 funded exchange project with South America.