Technical, Research Report
@TechReport
Technischer-, Forschungsbericht


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:









Author, Editor

Author(s):

Sanders, Peter
Pettie, Seth

dblp
dblp



Editor(s):





BibTeX Citekey*:

SandersPettie2004

Language:

English

Title, Institution

Title*:

A Simpler Linear Time 2/3 - epsilon Approximation for Maximum
Weight Matching

Institution*:

Max-Planck-Institut für Informatik

Publishers or Institutions Address*:

Stuhlsatzenhausweg 85, 66123 Saarbrücken, Germany

Type:

Research Report

No, Year, pp.,

Number*:

MPI-I-2004-1-002

Pages*:

10

Month:

January

VG Wort
Pages*:


Year*:

2004

ISBN/ISSN:

0946-011X





DOI:




Note, Abstract, ©

Note:


(LaTeX) Abstract:

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$.

Categories / Keywords:


Copyright Message:


HyperLinks / References / URLs:


Personal Comments:


File Upload:


Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

Expert

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat


BibTeX Entry:
@TECHREPORT{SandersPettie2004,
AUTHOR = {Sanders, Peter and Pettie, Seth},
TITLE = {A Simpler Linear Time 2/3 - epsilon Approximation for Maximum
Weight Matching
},
PUBLISHER = {AG 1 - Mehlhorn},
YEAR = {2004},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut für Informatik},
NUMBER = {MPI-I-2004-1-002},
PAGES = {10},
ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
MONTH = {January},
ISBN = {0946-011X},
}


Entry last modified by Christine Kiesel, 03/02/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Created
08/12/2005 12:13:30 PM
Revision
1.
0.


Editor
Christine Kiesel



Edit Date
12.08.2005 12:13:43



Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section
MPI-I-2004-1-002.ps
View attachments here: