---
_id: '11874'
abstract:
- lang: eng
  text: "We consider the problem of maintaining an approximately maximum (fractional)
    matching and an approximately minimum vertex cover in a dynamic graph. Starting
    with the seminal paper by Onak and Rubinfeld [STOC 2010], this problem has received
    significant attention in recent years. There remains, however, a polynomial gap
    between the best known worst case update time and the best known amortised update
    time for this problem, even after allowing for randomisation. Specifically, Bernstein
    and Stein [ICALP 2015, SODA 2016] have the best known worst case update time.
    They present a deterministic data structure with approximation ratio (3/2 + ∊)
    and worst case update time O(m1/4/ ∊2), where m is the number of edges in the
    graph. In recent past, Gupta and Peng [FOCS 2013] gave a deterministic data structure
    with approximation ratio (1+ ∊) and worst case update time  No known randomised
    data structure beats the worst case update times of these two results. In contrast,
    the paper by Onak and Rubinfeld [STOC 2010] gave a randomised data structure with
    approximation ratio O(1) and amortised update time O(log2 n), where n is the number
    of nodes in the graph. This was later improved by Baswana, Gupta and Sen [FOCS
    2011] and Solomon [FOCS 2016], leading to a randomised date structure with approximation
    ratio 2 and amortised update time O(1).\r\n\r\nWe bridge the polynomial gap between
    the worst case and amortised update times for this problem, without using any
    randomisation. We present a deterministic data structure with approximation ratio
    (2 + ∊) and worst case update time O(log3 n), for all sufficiently small constants
    ∊."
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 M, Nanongkai D. Fully dynamic approximate maximum
    matching and minimum vertex cover in o(log3 n) worst case update time. In: <i>28th
    Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Vol 0. Society for Industrial
    and Applied Mathematics; 2017:470-489. doi:<a href="https://doi.org/10.1137/1.9781611974782.30">10.1137/1.9781611974782.30</a>'
  apa: 'Bhattacharya, S., Henzinger, M., &#38; Nanongkai, D. (2017). Fully dynamic
    approximate maximum matching and minimum vertex cover in o(log3 n) worst case
    update time. In <i>28th Annual ACM-SIAM Symposium on Discrete Algorithms</i> (Vol.
    0, pp. 470–489). Barcelona, Spain: Society for Industrial and Applied Mathematics.
    <a href="https://doi.org/10.1137/1.9781611974782.30">https://doi.org/10.1137/1.9781611974782.30</a>'
  chicago: Bhattacharya, Sayan, Monika Henzinger, and Danupon Nanongkai. “Fully Dynamic
    Approximate Maximum Matching and Minimum Vertex Cover in o(Log3 n) Worst Case
    Update Time.” In <i>28th Annual ACM-SIAM Symposium on Discrete Algorithms</i>,
    0:470–89. Society for Industrial and Applied Mathematics, 2017. <a href="https://doi.org/10.1137/1.9781611974782.30">https://doi.org/10.1137/1.9781611974782.30</a>.
  ieee: S. Bhattacharya, M. Henzinger, and D. Nanongkai, “Fully dynamic approximate
    maximum matching and minimum vertex cover in o(log3 n) worst case update time,”
    in <i>28th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Barcelona, Spain,
    2017, vol. 0, pp. 470–489.
  ista: 'Bhattacharya S, Henzinger M, Nanongkai D. 2017. Fully dynamic approximate
    maximum matching and minimum vertex cover in o(log3 n) worst case update time.
    28th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete
    Algorithms vol. 0, 470–489.'
  mla: Bhattacharya, Sayan, et al. “Fully Dynamic Approximate Maximum Matching and
    Minimum Vertex Cover in o(Log3 n) Worst Case Update Time.” <i>28th Annual ACM-SIAM
    Symposium on Discrete Algorithms</i>, vol. 0, Society for Industrial and Applied
    Mathematics, 2017, pp. 470–89, doi:<a href="https://doi.org/10.1137/1.9781611974782.30">10.1137/1.9781611974782.30</a>.
  short: S. Bhattacharya, M. Henzinger, D. Nanongkai, in:, 28th Annual ACM-SIAM Symposium
    on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2017,
    pp. 470–489.
conference:
  end_date: 2017-01-19
  location: Barcelona, Spain
  name: 'SODA: Symposium on Discrete Algorithms'
  start_date: 2017-01-16
date_created: 2022-08-16T12:28:27Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2024-11-06T12:20:58Z
day: '01'
doi: 10.1137/1.9781611974782.30
extern: '1'
external_id:
  arxiv:
  - '1704.02844'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1704.02844
month: '01'
oa: 1
oa_version: Preprint
page: 470 - 489
publication: 28th Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
  eisbn:
  - 978-161197478-2
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Fully dynamic approximate maximum matching and minimum vertex cover in o(log3
  n) worst case update time
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: '0'
year: '2017'
...