Weighted Matching in the Semi-Streaming Model

Simple item page
dc.creatorZelke, Mariano
dc.date2007-09-21
dc.date.accessioned2026-07-07T09:22:42Z
dc.date.available2026-07-07T09:22:42Z
dc.descriptionWe reduce the best known approximation ratio for finding a weighted matching of a graph using a one-pass semi-streaming algorithm from 5.828 to 5.585. The semi-streaming model forbids random access to the input and restricts the memory to O(n*polylog(n)) bits. It was introduced by Muthukrishnan in 2003 and is appropriate when dealing with massive graphs.
dc.description12 pages, 2 figures
dc.identifierhttps://arxiv.org/abs/0709.3384
dc.identifierhttp://arxiv.org/abs/0709.3384
dc.identifierProceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science - STACS 2008, Bordeaux : France (2008)
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/155470
dc.subjectDiscrete Mathematics
dc.subjectData Structures and Algorithms
dc.subjectF.2.2; G.2.2
dc.titleWeighted Matching in the Semi-Streaming Model
dc.typetext

Files

Collections

arXiv