@inproceedings{80f4e1e4aac14051adc558b8dd36d15f,
title = "Electrical Flows for Polylogarithmic Competitive Oblivious Routing",
abstract = "Oblivious routing is a well-studied paradigm that uses static precomputed routing tables for selecting routing paths within a network. Existing oblivious routing schemes with polylogarithmic competitive ratio for general networks are tree-based, in the sense that routing is performed according to a convex combination of trees. However, this restriction to trees leads to a construction that has time quadratic in the size of the network and does not parallelize well. In this paper we study oblivious routing schemes based on electrical routing. In particular, we show that general networks with n vertices and m edges admit a routing scheme that has competitive ratio O(log2 n) and consists of a convex combination of only O(√ m) electrical routings. This immediately leads to an improved construction algorithm with time O(m3/2) that can also be implemented in parallel with O(√ m) depth.",
keywords = "electrical flows, oblivious routing",
author = "Gramoz Goranci and Monika Henzinger and Harald R{\"a}cke and Sushant Sachdeva and Sricharan, {A. R.}",
note = "Publisher Copyright: {\textcopyright} 2024 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.; 15th Innovations in Theoretical Computer Science Conference, ITCS 2024 ; Conference date: 30-01-2024 Through 02-02-2024",
year = "2024",
month = jan,
doi = "10.4230/LIPIcs.ITCS.2024.55",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Venkatesan Guruswami",
booktitle = "15th Innovations in Theoretical Computer Science Conference, ITCS 2024",
}