---
_id: '11923'
abstract:
- lang: eng
  text: "We consider the following online optimization problem. We are given a graph
    G and each vertex of the graph is assigned to one of ℓ servers, where servers
    have capacity k and we assume that the graph has ℓ · k vertices. Initially, G
    does not contain any edges and then the edges of G are revealed one-by-one. The
    goal is to design an online algorithm ONL, which always places the connected components
    induced by the revealed edges on the same server and never exceeds the server
    capacities by more than ∊k for constant ∊ > 0. Whenever ONL learns about a new
    edge, the algorithm is allowed to move vertices from one server to another. Its
    objective is to minimize the number of vertex moves. More specifically, ONL should
    minimize the competitive ratio: the total cost ONL incurs compared to an optimal
    offline algorithm OPT.\r\n\r\nThe problem was recently introduced by Henzinger
    et al. (SIGMETRICS'2019) and is related to classic online problems such as online
    paging and scheduling. It finds applications in the context of resource allocation
    in the cloud and for optimizing distributed data structures such as union–find
    data structures.\r\n\r\nOur main contribution is a polynomial-time randomized
    algorithm, that is asymptotically optimal: we derive an upper bound of O(log ℓ
    + log k) on its competitive ratio and show that no randomized online algorithm
    can achieve a competitive ratio of less than Ω(log ℓ + log k). We also settle
    the open problem of the achievable competitive ratio by deterministic online algorithms,
    by deriving a competitive ratio of Θ(ℓ log k); to this end, we present an improved
    lower bound as well as a deterministic polynomial-time online algorithm.\r\n\r\nOur
    algorithms rely on a novel technique which combines efficient integer programming
    with a combinatorial approach for maintaining ILP solutions. More precisely, we
    use an ILP to assign the connected components induced by the revealed edges to
    the servers; this is similar to existing approximation schemes for scheduling
    algorithms. However, we cannot obtain our competitive ratios if we run the ILP
    after each edge insertion. Instead, we identify certain types of edge insertions,
    after which we can manually obtain an optimal ILP solution at zero cost without
    resolving the ILP. We believe this technique is of independent interest and will
    find further applications in the future."
article_processing_charge: No
arxiv: 1
author:
- 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: Stefan
  full_name: Neumann, Stefan
  last_name: Neumann
- first_name: Harald
  full_name: Räcke, Harald
  last_name: Räcke
- first_name: Stefan
  full_name: Schmid, Stefan
  last_name: Schmid
citation:
  ama: 'Henzinger M, Neumann S, Räcke H, Schmid S. Tight bounds for online graph partitioning.
    In: <i>32nd Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Society for
    Industrial and Applied Mathematics; 2021:2799-2818. doi:<a href="https://doi.org/10.1137/1.9781611976465.166">10.1137/1.9781611976465.166</a>'
  apa: 'Henzinger, M., Neumann, S., Räcke, H., &#38; Schmid, S. (2021). Tight bounds
    for online graph partitioning. In <i>32nd Annual ACM-SIAM Symposium on Discrete
    Algorithms</i> (pp. 2799–2818). Alexandria, VA, United States: Society for Industrial
    and Applied Mathematics. <a href="https://doi.org/10.1137/1.9781611976465.166">https://doi.org/10.1137/1.9781611976465.166</a>'
  chicago: Henzinger, Monika, Stefan Neumann, Harald Räcke, and Stefan Schmid. “Tight
    Bounds for Online Graph Partitioning.” In <i>32nd Annual ACM-SIAM Symposium on
    Discrete Algorithms</i>, 2799–2818. Society for Industrial and Applied Mathematics,
    2021. <a href="https://doi.org/10.1137/1.9781611976465.166">https://doi.org/10.1137/1.9781611976465.166</a>.
  ieee: M. Henzinger, S. Neumann, H. Räcke, and S. Schmid, “Tight bounds for online
    graph partitioning,” in <i>32nd Annual ACM-SIAM Symposium on Discrete Algorithms</i>,
    Alexandria, VA, United States, 2021, pp. 2799–2818.
  ista: 'Henzinger M, Neumann S, Räcke H, Schmid S. 2021. Tight bounds for online
    graph partitioning. 32nd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA:
    Symposium on Discrete Algorithms, 2799–2818.'
  mla: Henzinger, Monika, et al. “Tight Bounds for Online Graph Partitioning.” <i>32nd
    Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Society for Industrial and
    Applied Mathematics, 2021, pp. 2799–818, doi:<a href="https://doi.org/10.1137/1.9781611976465.166">10.1137/1.9781611976465.166</a>.
  short: M. Henzinger, S. Neumann, H. Räcke, S. Schmid, in:, 32nd Annual ACM-SIAM
    Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics,
    2021, pp. 2799–2818.
conference:
  end_date: 2021-01-13
  location: Alexandria, VA, United States
  name: 'SODA: Symposium on Discrete Algorithms'
  start_date: 2021-01-10
date_created: 2022-08-18T10:31:58Z
date_published: 2021-01-01T00:00:00Z
date_updated: 2024-11-06T12:26:29Z
day: '01'
doi: 10.1137/1.9781611976465.166
extern: '1'
external_id:
  arxiv:
  - '2011.01017'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/2011.01017
month: '01'
oa: 1
oa_version: Preprint
page: 2799-2818
publication: 32nd Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
  eisbn:
  - 978-161197646-5
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Tight bounds for online graph partitioning
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...