License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2017.58
URN: urn:nbn:de:0030-drops-81944
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8194/
Go to the corresponding LIPIcs Volume Portal

Stubbs, Daniel ; Vassilevska Williams, Virginia

Metatheorems for Dynamic Weighted Matching

pdf-format:
LIPIcs-ITCS-2017-58.pdf (0.5 MB)

Abstract

We consider the maximum weight matching (MWM) problem in dynamic graphs. We provide two reductions. The first reduces the dynamic MWM problem on m-edge, n-node graphs with weights bounded by N to the problem with weights bounded by (n/eps)^2, so that if the MWM problem can be alpha-approximated with update time t(m,n,N), then it can also be (1+eps)alpha-approximated with update time O(t(m,n,(n/eps)^2)log^2 n+log n loglog N)). The second reduction reduces the dynamic MWM problem to the dynamic maximum cardinality matching (MCM) problem in which the graph is unweighted. This reduction shows that if there is an \alpha-approximation algorithm for MCM with update time t(m,n) in m-edge n-node graphs, then there is also a (2+eps)alpha-approximation algorithm for MWM with update time O(t(m,n)eps^{-2}log^2 N). We also obtain better bounds in our reductions if the ratio between the largest and the smallest edge weight is small. Combined with recent work on MCM, these two reductions substantially improve upon the state-of-the-art of dynamic MWM algorithms.

BibTeX - Entry

@InProceedings{stubbs_et_al:LIPIcs:2017:8194,
  author =	{Daniel Stubbs and Virginia Vassilevska Williams},
  title =	{{Metatheorems for Dynamic Weighted Matching}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{58:1--58:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Christos H. Papadimitriou},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8194},
  URN =		{urn:nbn:de:0030-drops-81944},
  doi =		{10.4230/LIPIcs.ITCS.2017.58},
  annote =	{Keywords: dynamic algorithms, maximum matching, maximum weight matching}
}

Keywords: dynamic algorithms, maximum matching, maximum weight matching
Collection: 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Issue Date: 2017
Date of publication: 28.11.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI