Simple Distributed Weighted Matchings

Abstract

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.

Cited by in corpus (10)

• Delay-Based Back-Pressure Scheduling in Multihop Wireless Networks
• Distributed algorithms for covering, packing and maximum weighted matching
• Distributed Vertex Cover Algorithms For Wireless Sensor Networks
• Display of 3D Illuminations using Flying Light Specks
• Optimal Resource Allocation and Relay Selection in Bandwidth Exchange Based Cooperative Forwarding
• SERENADE: A Parallel Randomized Algorithm Suite for Crossbar Scheduling in Input-Queued Switches
• Average-Case Analysis of Greedy Matching for D2D Resource Sharing
• A Greedy link scheduler for Wireless Networks having Gaussian Broadcast and Multiple Access Channels
• Distributed Double Auctions for Large-Scale Device-to-Device Resource Trading
• Cooperative Caching in Fog Radio Access Networks: A Graph-based Approach