Simple Distributed Weighted Matchings

Simple item page
dc.creatorHoepman, Jaap-Henk
dc.date2004-10-19
dc.date.accessioned2026-07-07T03:21:53Z
dc.date.available2026-07-07T03:21:53Z
dc.descriptionWattenhofer [WW04] derive a complicated distributed algorithm to compute a weighted matching of an arbitrary weighted graph, that is at most a factor 5 away from the maximum weighted matching of that graph. We show that a variant of the obvious sequential greedy algorithm [Pre99], that computes a weighted matching at most a factor 2 away from the maximum, is easily distributed. This yields the best known distributed approximation algorithm for this problem so far.
dc.identifierhttps://arxiv.org/abs/cs/0410047
dc.identifierhttp://arxiv.org/abs/cs/0410047
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/32377
dc.subjectDistributed, Parallel, and Cluster Computing
dc.subjectDiscrete Mathematics
dc.titleSimple Distributed Weighted Matchings
dc.typetext

Files

Collections

arXiv