---
_id: '12571'
abstract:
- lang: eng
  text: We consider the problems of maintaining approximate maximum matching and minimum
    vertex cover in a dynamic graph. Starting with the seminal work of Onak and Rubinfeld
    [STOC 2010], this problem has received significant attention in recent years.
    Very recently, extending the framework of Baswana, Gupta and Sen [FOCS 2011],
    Solomon [FOCS 2016] gave a randomized 2-approximation dynamic algorithm for this
    problem that has amortized update time of O(1) with high probability. We consider
    the natural open question of derandomizing this result. We present a new deterministic
    fully dynamic algorithm that maintains a O(1)-approximate minimum vertex cover
    and maximum fractional matching, with an amortized update time of O(1). Previously,
    the best deterministic algorithm for this problem was due to Bhattacharya, Henzinger
    and Italiano [SODA 2015]; it had an approximation ratio of (2+ϵ) and an amortized
    update time of O(logn/ϵ2). Our result can be generalized to give a fully dynamic
    O(f3)-approximation algorithm with O(f2) amortized update time for the hypergraph
    vertex cover and fractional matching problems, where every hyperedge has at most
    f vertices.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Sayan
  full_name: Bhattacharya, Sayan
  last_name: Bhattacharya
- first_name: Deeparnab
  full_name: Chakrabarty, Deeparnab
  last_name: Chakrabarty
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
citation:
  ama: 'Bhattacharya S, Chakrabarty D, Henzinger MH. Deterministic fully dynamic approximate
    vertex cover and fractional matching in O(1) amortized update time. In: <i>19th
    International Conference on Integer Programming and Combinatorial Optimization</i>.
    Vol 10328. Springer Nature; 2017:86-98. doi:<a href="https://doi.org/10.1007/978-3-319-59250-3_8">10.1007/978-3-319-59250-3_8</a>'
  apa: 'Bhattacharya, S., Chakrabarty, D., &#38; Henzinger, M. H. (2017). Deterministic
    fully dynamic approximate vertex cover and fractional matching in O(1) amortized
    update time. In <i>19th International Conference on Integer Programming and Combinatorial
    Optimization</i> (Vol. 10328, pp. 86–98). Waterloo, ON, Canada: Springer Nature.
    <a href="https://doi.org/10.1007/978-3-319-59250-3_8">https://doi.org/10.1007/978-3-319-59250-3_8</a>'
  chicago: Bhattacharya, Sayan, Deeparnab Chakrabarty, and Monika H Henzinger. “Deterministic
    Fully Dynamic Approximate Vertex Cover and Fractional Matching in O(1) Amortized
    Update Time.” In <i>19th International Conference on Integer Programming and Combinatorial
    Optimization</i>, 10328:86–98. Springer Nature, 2017. <a href="https://doi.org/10.1007/978-3-319-59250-3_8">https://doi.org/10.1007/978-3-319-59250-3_8</a>.
  ieee: S. Bhattacharya, D. Chakrabarty, and M. H. Henzinger, “Deterministic fully
    dynamic approximate vertex cover and fractional matching in O(1) amortized update
    time,” in <i>19th International Conference on Integer Programming and Combinatorial
    Optimization</i>, Waterloo, ON, Canada, 2017, vol. 10328, pp. 86–98.
  ista: 'Bhattacharya S, Chakrabarty D, Henzinger MH. 2017. Deterministic fully dynamic
    approximate vertex cover and fractional matching in O(1) amortized update time.
    19th International Conference on Integer Programming and Combinatorial Optimization.
    IPCO: Integer Programming and Combinatorial Optimization, LNCS, vol. 10328, 86–98.'
  mla: Bhattacharya, Sayan, et al. “Deterministic Fully Dynamic Approximate Vertex
    Cover and Fractional Matching in O(1) Amortized Update Time.” <i>19th International
    Conference on Integer Programming and Combinatorial Optimization</i>, vol. 10328,
    Springer Nature, 2017, pp. 86–98, doi:<a href="https://doi.org/10.1007/978-3-319-59250-3_8">10.1007/978-3-319-59250-3_8</a>.
  short: S. Bhattacharya, D. Chakrabarty, M.H. Henzinger, in:, 19th International
    Conference on Integer Programming and Combinatorial Optimization, Springer Nature,
    2017, pp. 86–98.
conference:
  end_date: 2017-06-28
  location: Waterloo, ON, Canada
  name: 'IPCO: Integer Programming and Combinatorial Optimization'
  start_date: 2017-06-26
date_created: 2023-02-20T07:52:31Z
date_published: 2017-05-24T00:00:00Z
date_updated: 2023-02-20T07:57:24Z
day: '24'
doi: 10.1007/978-3-319-59250-3_8
extern: '1'
external_id:
  arxiv:
  - '1611.00198'
intvolume: '     10328'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1611.00198
month: '05'
oa: 1
oa_version: Preprint
page: 86-98
publication: 19th International Conference on Integer Programming and Combinatorial
  Optimization
publication_identifier:
  eisbn:
  - '9783319592503'
  isbn:
  - '9783319592497'
  issn:
  - 0302-9743
  - 1611-3349
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Deterministic fully dynamic approximate vertex cover and fractional matching
  in O(1) amortized update time
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 10328
year: '2017'
...