 # Department of Computer Science and Information Systems

Search
Search our website:

# Hunter, Cauchy Rabbit, and Optimal Kakeya Sets

• Speaker: Dr Ron Peretz, Mathematics department, London School of Economics (LSE).
• Date: Wednesday, 22 January 2014 from 16:30 to 17:30
• Location: Room 160, Birkbeck Main Building

A Cauchy random walk will take us from a Hunter-Rabbit search game on the circle to the famous Kakeya problem and back.

Joint work with Y. Babichenko, Y. Peres, P. Sousi and P. Winkler. Professor Gregory Gutin, Department of Computer Science, Royal Hollaway, University of London.

Planning Snow Plowing in Berlin: Solving Parameterized Rural Postman Problem

seminar

Monday, 9th of December 2013, from 16:30 to 17:30

Room 160, Birkbeck Main Building

The Directed Rural Postman Problem (DRPP) can be formulated as follows: given a strongly connected directed multigraph $D=(V,A)$ with nonnegative integral weights on the arcs, a subset $R$ of $A$ and a nonnegative integer $\ell$, decide whether $D$ has a closed directed walk containing every arc of $R$ and of total weight at most $\ell$. DRPP is NP-complete. Let $k$ be the number of weakly connected components in the the subgraph of $D$ induced by $R$. Sorge et al. (2012) asked whether the DRPP is fixed-parameter tractable (FPT) when parameterized by $k$, i.e., whether there is an algorithm of running time $O^*(f(k))$ where $f$ is a function of $k$ only and the $O^*$ notation suppresses polynomial factors. Sorge et al. (2012) noted that this question is of significant practical relevance (in Snow Plowing in Berlin, k is between 3 and 5) and has been open for more than thirty years. Using an algebraic approach, we prove that DRPP has a randomized algorithm with false negatives of running time $O^*(2^k)$ when $\ell$ is bounded by a polynomial in the number of vertices in $D$. We also show that the same result holds for the undirected version of DRPP, where $D$ is a connected undirected multigraph.

Joint work with Magnus Wahlstrom and Anders Yeo.