Online Routing and Searching Problems

Professor Patrick Jaillet

ABSTRACT

An online problem is one that must be “solved” without knowing the future or without having complete information on the problem instance. In this talk we present recent work on parallel online searching of concurrent lines and on online traveling salesman problems. We first consider online problems where p searchers explore m>p half-lines, all joined at a common origin, and we discuss optimal deterministic on-line strategies for solving time-competitive and distance-competitive variants of the problem. We then present preliminary results associated with variants of the online TSP in various metric space. The second part of the talk is joint work with Michael Wagner, MIT ORC.