What is it about?

Suppose you want to build an *offline* navigation application where each driver enters their starting and destination city as inputs, and the app outputs the route along which to drive. Can we design an app that lets every driver arrive at their destination as fast as possible without explicitly coordinating the routes with other drivers? In this paper, we show that the answer is yes, building such an offline navigation app is possible if one is allowed to suffer a polylogarithmic loss factor.

Featured Image

Why is it important?

The question described above, also known as "oblivious routing for makespan minimization" (among other names) was an important open problem in the area of oblivious routings. This paper answers the question positively and opens a way for a multitude of theoretical advances by utilizing the methods developed in the paper.

Perspectives

This paper is an important part of a larger research program of "Universal optimality in distributed optimization", which aims to develop algorithms that are as fast as possible on every network. This ambitious goal spans many areas of computer science and facilitates idea exchange between them. Hop-constrained oblivious routings are a showcase of how ideas developed for distributed computing and information theory can help seemingly distant and unrelated areas. We hope that this exchange unlocks many new results.

Goran Zuzic
ETH Zürich, D-CHAB

Read the Original

This page is a summary of: Hop-constrained oblivious routing, June 2021, ACM (Association for Computing Machinery),
DOI: 10.1145/3406325.3451098.
You can read the full text:

Read

Resources

Contributors

The following have contributed to this page