Show simple item record

dc.contributor.author
Wattenhofer, Mirjam
dc.contributor.author
Wattenhofer, Roger
dc.date.accessioned
2017-08-14T06:50:21Z
dc.date.available
2017-06-10T19:28:37Z
dc.date.available
2017-08-14T06:50:21Z
dc.date.issued
2004
dc.identifier.uri
http://hdl.handle.net/20.500.11850/69753
dc.identifier.doi
10.3929/ethz-a-006733102
dc.description.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.
en_US
dc.language.iso
en
en_US
dc.publisher
ETH, Department of Computer Science
en_US
dc.rights.uri
http://rightsstatements.org/page/InC-NC/1.0/
dc.subject
Weighted matching
en_US
dc.subject
Approximation algorithms
en_US
dc.title
Fast and simple algorithms for weighted perfect matching
en_US
dc.type
Report
dc.rights.license
In Copyright - Non-Commercial Use Permitted
ethz.journal.title
Technical report
ethz.journal.volume
433
en_US
ethz.size
6 p.
en_US
ethz.code.ddc
0 - Computer science, information & general works::004 - Data processing, computer science
en_US
ethz.notes
Technical Reports D-INFK.
en_US
ethz.identifier.nebis
006733102
ethz.publication.place
Zurich
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02140 - Dep. Inf.technologie und Elektrotechnik / Dep. of Inform.Technol. Electrical Eng.::02640 - Inst. f. Technische Informatik und Komm. / Computer Eng. and Networks Lab.::03234 - Plattner, Bernhard (emeritus)
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02140 - Dep. Inf.technologie und Elektrotechnik / Dep. of Inform.Technol. Electrical Eng.::02640 - Inst. f. Technische Informatik und Komm. / Computer Eng. and Networks Lab.::03604 - Wattenhofer, Roger / Wattenhofer, Roger
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02140 - Dep. Inf.technologie und Elektrotechnik / Dep. of Inform.Technol. Electrical Eng.::02640 - Inst. f. Technische Informatik und Komm. / Computer Eng. and Networks Lab.::03604 - Wattenhofer, Roger / Wattenhofer, Roger
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02140 - Dep. Inf.technologie und Elektrotechnik / Dep. of Inform.Technol. Electrical Eng.::02640 - Inst. f. Technische Informatik und Komm. / Computer Eng. and Networks Lab.::03234 - Plattner, Bernhard (emeritus)
ethz.date.deposited
2017-06-10T19:28:47Z
ethz.source
ECOL
ethz.source
ECIT
ethz.identifier.importid
imp593650d2de7c460983
ethz.identifier.importid
imp59366b1391bc779857
ethz.ecolpid
eth:4711
ethz.ecitpid
pub:110456
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2017-07-13T04:49:29Z
ethz.rosetta.lastUpdated
2018-11-05T16:25:37Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Fast%20and%20simple%20algorithms%20for%20weighted%20perfect%20matching&rft.jtitle=Technical%20report&rft.date=2004&rft.volume=433&rft.au=Wattenhofer,%20Mirjam&Wattenhofer,%20Roger&rft.genre=report&
 Search via SFX

Files in this item

Thumbnail

Publication type

Show simple item record