2004/10/19 by Jaap-Henk Hoepman, Hoepman, Jaap-Henk · 2 citations
Computer Science · #Complexity and Algorithms in Graphs #Data Management and Algorithms #Discrete Mathematics (cs.DM) #Distributed #FOS: Computer and information sciences #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC) #cs.DC #cs.DM
paper · pdf · doi:10.48550/arxiv.cs/0410047
arxiv created 2004/10/19 · openalex publication_date 2004/10/19 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Wattenhofer [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.