Algorithms, Combinatorics and Optimization Seminar

For more information, please visit the home page for the program in Algorithms, Combinatorics and Optimization at Carnegie Mellon University.

Carnegie Mellon University offers an interdisciplinary Ph.D program in Algorithms, Combinatorics and Optimization. This program is the first of its kind in the United States. It is administered jointly by the Tepper School of Business (Operations Research group), the Computer Science Department (Algorithms and Complexity group) and the Department of Mathematical Sciences (Discrete Mathematics group). (Learn more...)

---

Nathasha Komarov
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