MPI-INF Logo
MPI-INF/SWS Research Reports 1991-2021

2. Number - only D1

MPI-I-2004-1-002

A simpler linear time 2/3 - epsilon approximation for maximum weight matching

Sanders, Peter and Pettie, Seth

January 2004, 10 pages.

.
Status: available - back from printing

We present two $\twothirds - \epsilon$ approximation algorithms for the maximum weight matching problem that run in time $O(m\log\frac{1}{\epsilon})$. We give a simple and practical randomized algorithm and a somewhat more complicated deterministic algorithm. Both algorithms are exponentially faster in terms of $\epsilon$ than a recent algorithm by Drake and Hougardy. We also show that our algorithms can be generalized to find a $1-\epsilon$ approximatation to the maximum weight matching, for any $\epsilon>0$.

  • MPI-I-2004-1-002.ps
  • Attachement: MPI-I-2004-1-002.ps (212 KBytes)

URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2004-1-002

Hide details for BibTeXBibTeX
@TECHREPORT{SandersPettie2004,
  AUTHOR = {Sanders, Peter and Pettie, Seth},
  TITLE = {A simpler linear time 2/3 - epsilon approximation for maximum weight matching},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-2004-1-002},
  MONTH = {January},
  YEAR = {2004},
  ISSN = {0946-011X},
}