Improved approximation guarantees for weighted matching in the semi-streaming model

Leah Epstein 1 Asaf Levin 2 Julián Mestre 3, * Danny Segev 4
* Auteur correspondant
1 Department of Mathematics
2 Faculty of Industrial Engineering and Management
3 MPII - Max-Planck-Institut für Informatik
4 Department of Statistics
Abstract : We study the maximum weight matching problem in the semi-streaming model, and improve on the currently best one-pass algorithm due to Zelke (Proc. of STACS2008, pages 669-680) by devising a deterministic approach whose performance guarantee is 4.91+epsilon. In addition, we study preemptive online algorithms, a sub-class of one-pass algorithms where we are only allowed to maintain a feasible matching in memory at any point in time. All known results prior to Zelke's belong to this sub-class. We provide a lower bound of 4.967 on the competitive ratio of any such deterministic algorithm, and hence show that future improvements will have to store in memory a set of edges which is not necessarily a feasible matching.
Type de document :
Communication dans un congrès
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.347-358, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00456411
Contributeur : Publications Loria <>
Soumis le : lundi 15 février 2010 - 10:32:52
Dernière modification le : dimanche 31 décembre 2017 - 09:44:02
Document(s) archivé(s) le : vendredi 18 juin 2010 - 20:37:26

Fichier

epstein.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00456411, version 1

Collections

STACS2010

Citation

Leah Epstein, Asaf Levin, Julián Mestre, Danny Segev. Improved approximation guarantees for weighted matching in the semi-streaming model. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.347-358, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00456411〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

141

Téléchargements de fichiers

133

Contact


archive-ouverte@inria.fr