"On Voting Caterpillars:
Approximating Maximum Degree in a Tournament by Binary Trees"

Speaker: Ariel Procaccia
Date: Thursday, 3 April 2008
Time: 2pm
Place: Ross 201

Abstract:

Voting trees describe an iterative procedure for selecting a single
vertex from a tournament. It has long been known that there is no
voting tree that always singles out a vertex with maximum degree. In
this paper, we study the power of voting trees in approximating the
maximum degree.  We give upper and lower bounds on the worst-case
ratio between the degree of the vertex chosen by a tree and the
maximum degree, both for the deterministic model concerned with a
single fixed tree, and for randomizations over arbitrary sets of
trees. Our main positive result is a randomization over surjective
trees of polynomial size that provides an approximation ratio of at
least 1/2. The proof is based on a connection between a randomization
over caterpillar trees and a rapidly mixing Markov chain.

Joint work with Felix Fischer and Alex Samorodnitsky.