---
_id: '11866'
abstract:
- lang: eng
  text: "We present a deterministic (1+o(1))-approximation O(n1/2+o(1)+D1+o(1))-time
    algorithm for solving the single-source shortest paths problem on distributed
    weighted networks (the CONGEST model); here n is the number of nodes in the network
    and D is its (hop) diameter. This is the first non-trivial deterministic algorithm
    for this problem. It also improves (i) the running time of the randomized (1+o(1))-approximation
    Õ(n1/2D1/4+D)-time algorithm of Nanongkai [STOC 2014] by a factor of as large
    as n1/8, and (ii) the O(є−1logє−1)-approximation factor of Lenzen and Patt-Shamir’s
    Õ(n1/2+є+D)-time algorithm [STOC 2013] within the same running time. Our running
    time matches the known time lower bound of Ω(n1/2/logn + D) [Das Sarma et al.
    STOC 2011] modulo some lower-order terms, thus essentially settling the status
    of this problem which was raised at least a decade ago [Elkin SIGACT News 2004].
    It also implies a (2+o(1))-approximation O(n1/2+o(1)+D1+o(1))-time algorithm for
    approximating a network’s weighted diameter which almost matches the lower bound
    by Holzer et al. [PODC 2012].\r\n\r\nIn achieving this result, we develop two
    techniques which might be of independent interest and useful in other settings:
    (i) a deterministic process that replaces the “hitting set argument” commonly
    used for shortest paths computation in various settings, and (ii) a simple, deterministic,
    construction of an (no(1), o(1))-hop set of size O(n1+o(1)). We combine these
    techniques with many distributed algorithmic techniques, some of which from problems
    that are not directly related to shortest paths, e.g. ruling sets [Goldberg et
    al. STOC 1987], source detection [Lenzen, Peleg PODC 2013], and partial distance
    estimation [Lenzen, Patt-Shamir PODC 2015]. Our hop set construction also leads
    to single-source shortest paths algorithms in two other settings: (i) a (1+o(1))-approximation
    O(no(1))-time algorithm on congested cliques, and (ii) a (1+o(1))-approximation
    O(no(1)logW)-pass O(n1+o(1)logW)-space streaming algorithm, when edge weights
    are in {1, 2, …, W}. The first result answers an open problem in [Nanongkai, STOC
    2014]. The second result partially answers an open problem raised by McGregor
    in 2006 [<pre>sublinear.info</pre>, Problem 14]."
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: Sebastian
  full_name: Krinninger, Sebastian
  last_name: Krinninger
- first_name: Danupon
  full_name: Nanongkai, Danupon
  last_name: Nanongkai
citation:
  ama: 'Henzinger MH, Krinninger S, Nanongkai D. A deterministic almost-tight distributed
    algorithm for approximating single-source shortest paths. In: <i>48th Annual ACM
    SIGACT Symposium on Theory of Computing</i>. Association for Computing Machinery;
    2016:489-498. doi:<a href="https://doi.org/10.1145/2897518.2897638">10.1145/2897518.2897638</a>'
  apa: 'Henzinger, M. H., Krinninger, S., &#38; Nanongkai, D. (2016). A deterministic
    almost-tight distributed algorithm for approximating single-source shortest paths.
    In <i>48th Annual ACM SIGACT Symposium on Theory of Computing</i> (pp. 489–498).
    Cambridge, MA, United States: Association for Computing Machinery. <a href="https://doi.org/10.1145/2897518.2897638">https://doi.org/10.1145/2897518.2897638</a>'
  chicago: Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “A Deterministic
    Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths.”
    In <i>48th Annual ACM SIGACT Symposium on Theory of Computing</i>, 489–98. Association
    for Computing Machinery, 2016. <a href="https://doi.org/10.1145/2897518.2897638">https://doi.org/10.1145/2897518.2897638</a>.
  ieee: M. H. Henzinger, S. Krinninger, and D. Nanongkai, “A deterministic almost-tight
    distributed algorithm for approximating single-source shortest paths,” in <i>48th
    Annual ACM SIGACT Symposium on Theory of Computing</i>, Cambridge, MA, United
    States, 2016, pp. 489–498.
  ista: 'Henzinger MH, Krinninger S, Nanongkai D. 2016. A deterministic almost-tight
    distributed algorithm for approximating single-source shortest paths. 48th Annual
    ACM SIGACT Symposium on Theory of Computing. STOC: Symposium on Theory of Computing,
    489–498.'
  mla: Henzinger, Monika H., et al. “A Deterministic Almost-Tight Distributed Algorithm
    for Approximating Single-Source Shortest Paths.” <i>48th Annual ACM SIGACT Symposium
    on Theory of Computing</i>, Association for Computing Machinery, 2016, pp. 489–98,
    doi:<a href="https://doi.org/10.1145/2897518.2897638">10.1145/2897518.2897638</a>.
  short: M.H. Henzinger, S. Krinninger, D. Nanongkai, in:, 48th Annual ACM SIGACT
    Symposium on Theory of Computing, Association for Computing Machinery, 2016, pp.
    489–498.
conference:
  end_date: 2016-06-21
  location: Cambridge, MA, United States
  name: 'STOC: Symposium on Theory of Computing'
  start_date: 2016-06-19
date_created: 2022-08-16T09:19:31Z
date_published: 2016-06-01T00:00:00Z
date_updated: 2023-02-17T10:32:23Z
day: '01'
doi: 10.1145/2897518.2897638
extern: '1'
external_id:
  arxiv:
  - '1504.07056'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1504.07056
month: '06'
oa: 1
oa_version: Preprint
page: 489 - 498
publication: 48th Annual ACM SIGACT Symposium on Theory of Computing
publication_identifier:
  isbn:
  - 978-145034132-5
  issn:
  - 0737-8017
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: A deterministic almost-tight distributed algorithm for approximating single-source
  shortest paths
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2016'
...
---
_id: '11867'
abstract:
- lang: eng
  text: We present two deterministic dynamic algorithms for the maximum matching problem.
    (1) An algorithm that maintains a (2+є)-approximate maximum matching in general
    graphs with O(poly(logn, 1/є)) update time. (2) An algorithm that maintains an
    αK approximation of the value of the maximum matching with O(n2/K) update time
    in bipartite graphs, for every sufficiently large constant positive integer K.
    Here, 1≤ αK < 2 is a constant determined by the value of K. Result (1) is the
    first deterministic algorithm that can maintain an o(logn)-approximate maximum
    matching with polylogarithmic update time, improving the seminal result of Onak
    et al. [STOC 2010]. Its approximation guarantee almost matches the guarantee of
    the best randomized polylogarithmic update time algorithm [Baswana et al. FOCS
    2011]. Result (2) achieves a better-than-two approximation with arbitrarily small
    polynomial update time on bipartite graphs. Previously the best update time for
    this problem was O(m1/4) [Bernstein et al. ICALP 2015], where m is the current
    number of edges in the graph.
article_processing_charge: No
arxiv: 1
author:
- first_name: Sayan
  full_name: Bhattacharya, Sayan
  last_name: Bhattacharya
- 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: Danupon
  full_name: Nanongkai, Danupon
  last_name: Nanongkai
citation:
  ama: 'Bhattacharya S, Henzinger MH, Nanongkai D. New deterministic approximation
    algorithms for fully dynamic matching. In: <i>48th Annual ACM SIGACT Symposium
    on Theory of Computing</i>. Association for Computing Machinery; 2016:398-411.
    doi:<a href="https://doi.org/10.1145/2897518.2897568">10.1145/2897518.2897568</a>'
  apa: 'Bhattacharya, S., Henzinger, M. H., &#38; Nanongkai, D. (2016). New deterministic
    approximation algorithms for fully dynamic matching. In <i>48th Annual ACM SIGACT
    Symposium on Theory of Computing</i> (pp. 398–411). Cambridge, MA, United States:
    Association for Computing Machinery. <a href="https://doi.org/10.1145/2897518.2897568">https://doi.org/10.1145/2897518.2897568</a>'
  chicago: Bhattacharya, Sayan, Monika H Henzinger, and Danupon Nanongkai. “New Deterministic
    Approximation Algorithms for Fully Dynamic Matching.” In <i>48th Annual ACM SIGACT
    Symposium on Theory of Computing</i>, 398–411. Association for Computing Machinery,
    2016. <a href="https://doi.org/10.1145/2897518.2897568">https://doi.org/10.1145/2897518.2897568</a>.
  ieee: S. Bhattacharya, M. H. Henzinger, and D. Nanongkai, “New deterministic approximation
    algorithms for fully dynamic matching,” in <i>48th Annual ACM SIGACT Symposium
    on Theory of Computing</i>, Cambridge, MA, United States, 2016, pp. 398–411.
  ista: 'Bhattacharya S, Henzinger MH, Nanongkai D. 2016. New deterministic approximation
    algorithms for fully dynamic matching. 48th Annual ACM SIGACT Symposium on Theory
    of Computing. STOC: Symposium on Theory of Computing, 398–411.'
  mla: Bhattacharya, Sayan, et al. “New Deterministic Approximation Algorithms for
    Fully Dynamic Matching.” <i>48th Annual ACM SIGACT Symposium on Theory of Computing</i>,
    Association for Computing Machinery, 2016, pp. 398–411, doi:<a href="https://doi.org/10.1145/2897518.2897568">10.1145/2897518.2897568</a>.
  short: S. Bhattacharya, M.H. Henzinger, D. Nanongkai, in:, 48th Annual ACM SIGACT
    Symposium on Theory of Computing, Association for Computing Machinery, 2016, pp.
    398–411.
conference:
  end_date: 2016-06-21
  location: Cambridge, MA, United States
  name: 'STOC: Symposium on Theory of Computing'
  start_date: 2016-06-19
date_created: 2022-08-16T09:27:35Z
date_published: 2016-06-01T00:00:00Z
date_updated: 2023-02-17T11:08:19Z
day: '01'
doi: 10.1145/2897518.2897568
extern: '1'
external_id:
  arxiv:
  - '1604.05765'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1604.05765
month: '06'
oa: 1
oa_version: Preprint
page: 398 - 411
publication: 48th Annual ACM SIGACT Symposium on Theory of Computing
publication_identifier:
  isbn:
  - 978-145034132-5
  issn:
  - 0737-8017
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: New deterministic approximation algorithms for fully dynamic matching
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2016'
...