Speaker: |
Tom Hayes (University of New Mexico Department of Computer Science Albuquerque, NM 87131 United States of America ) |

Organiser: |
Rahul Vaze |

Date: |
Tuesday, 15 Nov 2016, 16:00 to 17:00 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

We change perspective slightly: instead of minimizing the expected meeting time, we seek to maximize the probability of meeting within a specified time T. The Anderson-Weber strategy, which fails with constant probability when , is not asymptotically optimal for large T in this setting. Specifically, we exhibit a symmetric strategy that succeeds with probability in steps. This is tight: for any , any symmetric strategy with fails with constant probability. Our strategy uses a new combinatorial object that we dub a “rendezvous code,” which may be of independent interest.

When , we show that the probability of meeting within T steps is indeed asymptotically maximized by the Anderson-Weber strategy. Our results imply new lower bounds, showing that the best symmetric strategy takes at least steps in expectation. We also present some partial results for the symmetric rendezvous problem on other vertex-transitive graphs. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 742–765, 2016.