@inproceedings{12571,
  abstract     = {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.},
  author       = {Bhattacharya, Sayan and Chakrabarty, Deeparnab and Henzinger, Monika H},
  booktitle    = {19th International Conference on Integer Programming and Combinatorial Optimization},
  isbn         = {9783319592497},
  issn         = {0302-9743},
  location     = {Waterloo, ON, Canada},
  pages        = {86--98},
  publisher    = {Springer Nature},
  title        = {{Deterministic fully dynamic approximate vertex cover and fractional matching in O(1) amortized update time}},
  doi          = {10.1007/978-3-319-59250-3_8},
  volume       = {10328},
  year         = {2017},
}