Speaker: Heiko Roeglin Microsoft Research Asia
Time: 2008-06-25 14:00-2008-06-25 15:00
Venue: FIT Building 4-603, Tsinghua University
Download: Click!

Abstract:

 We analyze the complexity of integer optimization problems in the framework of smoothed analysis. This framework is based on a semi-random input model in which an adversary specifies an input that is subsequently perturbed at random. Smoothed analysis is a hybrid of average-case and worst-case analysis and it was introduced to explain the success of the simplex method in practice. In this talk, we characterize the class of integer optimization problems that have polynomial smoothed complexity in terms of their worst-case complexity.Essentially, we show that exactly those integer optimization problems have polynomial smoothed complexity that can be solved in pseudo-polynomial time in the worst case. A crucial ingredient of this characterization, which is also interesting on its own, is the observation that the smoothed number of Pareto-optimal solutions in bicriteria integer optimization problems is polynomial.
        This talk is based on joint work with Rene Beier and Berthold Voecking.

Short Bio:

Dr. Heiko Roeglin completed his PhD study in the Algorithms and Complexity group at RWTH Aachen University headed by Berthold Vöcking. His thesis is entitled "The Complexity of Nash Equilibria, Local Optima, and Pareto-Optimal Solutions". Currently he is a visiting researcher at the theory group of Microsoft Research Asia in Beijing. From July 2008 to June 2009 he will be a postdoctoral researcher at Boston University working with Shang-Hua Teng.