Open access
Date
2004Type
- Report
ETH Bibliography
yes
Altmetrics
Abstract
We present two fast and simple combinatorial approximation algorithms for constructing a minimum-weighted perfect matching on complete graphs whose cost functions satisfy the triangle inequality. The rst algorithm runs in O(n2 log n) time and is at most a factor log n worse than an optimal solution. In the second algorithm, the average time until a node is matched is O(n2) and the approximation ratio is log2 n. Show more
Permanent link
https://doi.org/10.3929/ethz-a-006733102Publication status
publishedJournal / series
Technical Report / ETH Zurich, Department of Computer ScienceVolume
Publisher
ETH Zurich, Department of Computer ScienceSubject
Weighted matching; Approximation algorithmsOrganisational unit
03234 - Plattner, Bernhard (emeritus) / Plattner, Bernhard (emeritus)
02150 - Dep. Informatik / Dep. of Computer Science
03604 - Wattenhofer, Roger / Wattenhofer, Roger
Notes
Technical Reports D-INFK.More
Show all metadata
ETH Bibliography
yes
Altmetrics