---
_id: '15008'
abstract:
- lang: eng
  text: "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. \r\nIn
    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(log² n) and consists of a convex combination
    of only O(√m) electrical routings. This immediately leads to an improved construction
    algorithm with time Õ(m^{3/2}) that can also be implemented in parallel with
    Õ(√m) depth."
acknowledgement: "Monika Henzinger and A. R. Sricharan: This project has received
  funding from the European Research Council (ERC) under the European Union’s Horizon
  2020 research and innovation\r\nprogramme (Grant agreement No. 101019564) and the
  Austrian Science Fund (FWF) project Z\r\n422-N, project I 5982-N, and project P
  33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024.\r\nHarald
  Räcke: Research supported by German Research Foundation (DFG), grant 470029389\r\n(FlexNets),
  2021-2024.\r\nSushant Sachdeva: SS’s work is supported by an Natural Sciences and
  Engineering Research Council of Canada (NSERC) Discovery Grant RGPIN-2018-06398
  and a Sloan Research Fellowship."
alternative_title:
- LIPIcs
article_number: '55'
article_processing_charge: No
arxiv: 1
author:
- first_name: Gramoz
  full_name: Goranci, Gramoz
  last_name: Goranci
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Harald
  full_name: Räcke, Harald
  last_name: Räcke
- first_name: Sushant
  full_name: Sachdeva, Sushant
  last_name: Sachdeva
- first_name: A. R.
  full_name: Sricharan, A. R.
  last_name: Sricharan
citation:
  ama: 'Goranci G, Henzinger MH, Räcke H, Sachdeva S, Sricharan AR. Electrical flows
    for polylogarithmic competitive oblivious routing. In: <i>15th Innovations in
    Theoretical Computer Science Conference</i>. Vol 287. Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik; 2024. doi:<a href="https://doi.org/10.4230/LIPIcs.ITCS.2024.55">10.4230/LIPIcs.ITCS.2024.55</a>'
  apa: 'Goranci, G., Henzinger, M. H., Räcke, H., Sachdeva, S., &#38; Sricharan, A.
    R. (2024). Electrical flows for polylogarithmic competitive oblivious routing.
    In <i>15th Innovations in Theoretical Computer Science Conference</i> (Vol. 287).
    Berkeley, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
    <a href="https://doi.org/10.4230/LIPIcs.ITCS.2024.55">https://doi.org/10.4230/LIPIcs.ITCS.2024.55</a>'
  chicago: Goranci, Gramoz, Monika H Henzinger, Harald Räcke, Sushant Sachdeva, and
    A. R. Sricharan. “Electrical Flows for Polylogarithmic Competitive Oblivious Routing.”
    In <i>15th Innovations in Theoretical Computer Science Conference</i>, Vol. 287.
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href="https://doi.org/10.4230/LIPIcs.ITCS.2024.55">https://doi.org/10.4230/LIPIcs.ITCS.2024.55</a>.
  ieee: G. Goranci, M. H. Henzinger, H. Räcke, S. Sachdeva, and A. R. Sricharan, “Electrical
    flows for polylogarithmic competitive oblivious routing,” in <i>15th Innovations
    in Theoretical Computer Science Conference</i>, Berkeley, CA, United States, 2024,
    vol. 287.
  ista: 'Goranci G, Henzinger MH, Räcke H, Sachdeva S, Sricharan AR. 2024. Electrical
    flows for polylogarithmic competitive oblivious routing. 15th Innovations in Theoretical
    Computer Science Conference. ITCS: Innovations in Theoretical Computer Science
    Conference, LIPIcs, vol. 287, 55.'
  mla: Goranci, Gramoz, et al. “Electrical Flows for Polylogarithmic Competitive Oblivious
    Routing.” <i>15th Innovations in Theoretical Computer Science Conference</i>,
    vol. 287, 55, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a
    href="https://doi.org/10.4230/LIPIcs.ITCS.2024.55">10.4230/LIPIcs.ITCS.2024.55</a>.
  short: G. Goranci, M.H. Henzinger, H. Räcke, S. Sachdeva, A.R. Sricharan, in:, 15th
    Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2024.
conference:
  end_date: 2024-02-02
  location: Berkeley, CA, United States
  name: 'ITCS: Innovations in Theoretical Computer Science Conference'
  start_date: 2024-01-30
date_created: 2024-02-18T23:01:02Z
date_published: 2024-01-24T00:00:00Z
date_updated: 2025-07-15T12:51:53Z
day: '24'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ITCS.2024.55
ec_funded: 1
external_id:
  arxiv:
  - '2303.02491'
file:
- access_level: open_access
  checksum: b89716aae6a5599f187897e39de1e53a
  content_type: application/pdf
  creator: dernst
  date_created: 2024-02-26T10:10:48Z
  date_updated: 2024-02-26T10:10:48Z
  file_id: '15030'
  file_name: 2024_LIPICs_Goranci.pdf
  file_size: 1054754
  relation: main_file
  success: 1
file_date_updated: 2024-02-26T10:10:48Z
has_accepted_license: '1'
intvolume: '       287'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
  call_identifier: H2020
  grant_number: '101019564'
  name: The design and evaluation of modern fully dynamic data structures
- _id: 34def286-11ca-11ed-8bc3-da5948e1613c
  grant_number: Z00422
  name: Wittgenstein Award - Monika Henzinger
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
  grant_number: I05982
  name: Static and Dynamic Hierarchical Graph Decompositions
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
  grant_number: 'P33775 '
  name: Fast Algorithms for a Reactive Network Layer
publication: 15th Innovations in Theoretical Computer Science Conference
publication_identifier:
  isbn:
  - '9783959773096'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Electrical flows for polylogarithmic competitive oblivious routing
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 287
year: '2024'
...