Events - Colloquia & Seminars

CCIS Colloquium Spring 2006

Optimal Cover Time for a Graph-Based Coupon Collector Process

Speaker: Greg Plaxton

Affiliation: University of Texas at Austin

Date: Monday, April 10, 2006

Talk: 10:30 am, 366 WVH

Abstract

In this talk we study the following covering process defined over an arbitrary directed graph. Each node is initially uncovered and is assigned a random integer rank drawn from a suitable range. The process then proceeds in rounds. In each round, a uniformly random node is selected and its lowest-ranked uncovered outgoing neighbor, if any, is covered. We prove that if each node has in-degree $\Theta(d)$ and out-degree $O(d)$, then with high probability, every node is covered within $O(n+\frac{n\log n}{d})$ rounds, matching a lower bound due to Alon. Alon has also shown that, for a certain class of $d$-regular expander graphs, the upper bound holds no matter what method is used to choose the uncovered neighbor. In contrast, we show that for arbitrary $d$-regular graphs, the method used to choose the uncovered neighbor can affect the cover time by more than a constant factor.

Joint work with Ned Dimitrov.

Biography

Greg Plaxton is a Professor of Computer Science at the University of Texas at Austin. Greg received his Bachelor's degree from the University of Toronto in 1985 and his PhD in Computer Science from Stanford University in 1989. Following postdoctoral work at MIT, Greg joined the faculty at UT Austin in 1990. Begining in January 2000, he took a two-year leave of absence from UT Austin to work as a senior research scientist at Akamai Technologies. Greg's research spans the fields of parallel and distributed computing, analysis of algorithms, lower bounds, and randomization, and includes contributions related to sorting networks, peer-to-peer networks, fair scheduling, facility location, and clustering.