Improved approximation guarantees for weighted matching in the semi-streaming model - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2010

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

Leah Epstein
  • Fonction : Auteur
  • PersonId : 867233
Asaf Levin
  • Fonction : Auteur
  • PersonId : 867234
Danny Segev
  • Fonction : Auteur
  • PersonId : 867235

Résumé

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.
Fichier principal
Vignette du fichier
epstein.pdf (168.69 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00456411 , version 1 (15-02-2010)

Identifiants

  • HAL Id : inria-00456411 , version 1

Citer

Leah Epstein, Asaf Levin, Julián Mestre, Danny Segev. Improved approximation guarantees for weighted matching in the semi-streaming model. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Inria Nancy Grand Est & Loria, Mar 2010, Nancy, France. pp.347-358. ⟨inria-00456411⟩

Collections

STACS2010
80 Consultations
219 Téléchargements

Partager

Gmail Facebook X LinkedIn More