## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, September 18, 2018, 12:15 pm

Duration: 30 minutes

Location: CAB G51

Speaker: Pascal Pfister

## Optimal strategies for patrolling fences

A classical multi-agent fence patrolling problem asks: What is the maximum length L of a line that k agents with maximum speeds v_1,...,v_k can patrol if each point on the line needs to be visited at least once every unit of time. It is easy to see that L = a\sum_{i=1}^k v_i for some efficiency 1/2 ≤ a < 1. After a series of works giving better and better efficiencies, it was conjectured that the best possible efficiency approaches 2/3. We constructed a scheme whose efficiency is equal to 1 - \theta(1/\sqrt{k}), thus disproving the above conjecture of Kawamura and Kobayashi. Moreover, we also provide an asymtotically matching upper bound for a.

Information for students and suggested topics for student talks