[Colloq] Reminder: Greg Plaxton, Today, April, 10, 10:30am

[Rachel Kalweit]

College of Computer and Information Science Colloquium

Presents:
Greg Plaxton
University of Texas at Austin

Who will speak on:
Optimal Cover Time for a Graph-Based Coupon Collector Process

Monday, April 10, 2006
10:30am
366 West Village H
Northeastern University


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.

Host: Ravi Sundaram

_______________________________________________
Colloq mailing list
Colloq at lists.ccs.neu.edu
https://lists.ccs.neu.edu/bin/listinfo/colloq