Simple Distributed Weighted Matchings
<|reference_start|>Simple Distributed Weighted Matchings: 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.<|reference_end|>
@article{hoepman2004simple,
    title={Simple Distributed Weighted Matchings},
    author={Jaap-Henk Hoepman},
    journal={arXiv preprint arXiv:cs/0410047},
    year={2004},
    archivePrefix={arXiv},
    eprint={cs/0410047},
    primaryClass={cs.DC cs.DM}
}