Group:Algorithms Group
Title: Multiplying Pessimistic Estimators: Deterministic Approximation of Max TSP and M
Speaker: Anke van Zuylen University
Time: 2010-07-13 14:00-2010-07-13 15:00
Venue: FIT 1-222

Abstract:

This is going to be a practice talk for COCOON. In the paper, we give a generalization of the method of pessimistic estimators, in which we compose estimators by multiplying them. This leads to simple derandomizations of all known approximation algorithms for the maximum traveling salesman problem and the maximum triangle packing problem. In the talk, I will give a brief introduction to pessimistic estimators, and give an indication of why derandomization of the algorithms we consider seems non-trivial. Finally, I will try to convince you that with the idea of multiplying pessimistic estimators, derandomization does become quite simple.