Department of Mathematical Sciences
Events
People
Colloquia and Seminars
Conferences
Centers
Positions
Areas of Research
About the Department
Alumni |
Algorithms, Combinatorics and Optimization Seminar
Carnegie Mellon University Title: Cop vs. Gambler Abstract: We consider a variation of cop vs. robber on graph. The robber is not restricted by the graph edges and instead picks a time-independent probability distribution on V(G) and moves according to this fixed distribution. The cop moves from vertex to adjacent vertex with the goal of minimizing expected capture time. Players move simultaneously. We show that when the distribution is known, the expected capture time (with best play) on any connected n-vertex graph is exactly n. Time permitting, we will also discuss what is known about the case of an unknown distribution. Date: Thursday, September 12, 2013 Time: 3:30 pm Location: Wean Hall 8220 |