This paper presents an algorithm for estimating the weight of a maximum weighted matching by augmenting any estimation routine for the size of an unweighted matching. The algorithm is implementable in any streaming model including dynamic graph streams. We also give the first constant estimation for the maximum matching size in a dynamic graph stream for planar graphs (or any graph with bounded arboricity) using O~(n4/5) space which also extends to weighted matching. Using previous results by Kapralov, Khanna, and Sudan (2014) we obtain a polylog(n) approximation for general graphs using polylog(n) space in random order streams, respectively. In addition, we give a space lower bound of Ω(n1 − ε) for any randomized algorithm estimating the size of a maximum matching up to a 1 + O(ε) factor for adversarial streams.
Sublinear estimation of weighted matchings in dynamic data streams / Bury, Marc; Schwiegelshohn, Chris. - ELETTRONICO. - 9294:(2015), pp. 263-274. (Intervento presentato al convegno 23rd European Symposium on Algorithms, ESA 2015 tenutosi a Patras; Greece nel 2015) [10.1007/978-3-662-48350-3_23].
Sublinear estimation of weighted matchings in dynamic data streams
Schwiegelshohn, Chris
2015
Abstract
This paper presents an algorithm for estimating the weight of a maximum weighted matching by augmenting any estimation routine for the size of an unweighted matching. The algorithm is implementable in any streaming model including dynamic graph streams. We also give the first constant estimation for the maximum matching size in a dynamic graph stream for planar graphs (or any graph with bounded arboricity) using O~(n4/5) space which also extends to weighted matching. Using previous results by Kapralov, Khanna, and Sudan (2014) we obtain a polylog(n) approximation for general graphs using polylog(n) space in random order streams, respectively. In addition, we give a space lower bound of Ω(n1 − ε) for any randomized algorithm estimating the size of a maximum matching up to a 1 + O(ε) factor for adversarial streams.File | Dimensione | Formato | |
---|---|---|---|
Bury_Sublinear-estimation_2016.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
268.41 kB
Formato
Adobe PDF
|
268.41 kB | Adobe PDF | Contatta l'autore |
Bury_Frontespizio-indice_Sublinear-estimation_2016.pdf
solo gestori archivio
Tipologia:
Altro materiale allegato
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
176.67 kB
Formato
Adobe PDF
|
176.67 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.