Online Graph Exploration – Old and New Results

Exploring unknown environments is a fundamental task in many domains, e.g., robot navigation, network security, and internet search. In this talk, we give an overview of the current state of the art in online graph exploration in the fixed graph scenario. We provide details and lower bound examples of some algorithms such as the Nearest Neighbour (NN) algorithm with its competitive ratio of O(log n).

Afterwards, we design a general framework to robustify algorithms that carefully interpolates between a given algorithm and NN. We prove new performance bounds that leverage the individual good performance on particular inputs while establishing robustness to arbitrary inputs. This robustification schemes also allows us to initiate the study of a learning-augmented variant of the problem by adding access to machine-learned predictions and naturally integrating these predictions into the NN algorithm. This method significantly outperforms any known online algorithm if the prediction is of high accuracy while maintaining good guarantees when the prediction is of poor quality.

This is based on joint work with Alexander Lindermayr, Nicole Megow, Lukas Nölke, and Jens Schlöter, all from University of Bremen, Germany.