Elias
Elias Koutsoupias
Professor of Computer Science
University of Athens
Panepistimiopolis, Ilissia
Athens 15784
Greece

phone: +30 210 7275122
fax: +30 210 7275114

C. Brito, E. Koutsoupias, and S. Vaya. Competitive analysis of organization networks or multicast acknowledgement: how much to wait? In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 627--635, New Orleans, Louisiana, USA, January 11-14, 2004.
Download: pdf ps

Abstract

We study, from the competitive analysis perspective, the trade off between communication cost and delay cost (or simply the send-or-wait dilemma) on a hierarchy (rooted tree). The problem is an abstraction of the message aggregation problem on communication networks and the organizational problem in network hierarchies. We consider the most natural variant of the problem, the distributed asynchronous regime, and give tight (within an additive constant) upper and lower bounds of the competitive ratio. We also consider the centralized version of the problem, where we combine the natural rent-to-buy strategy with prediction techniques to achieve the first constant competitive ratio algorithm for any non-trivial class of network topologies.

Bib

@string{SODA04 = {Proceedings of the ACM-SIAM Symposium on Discrete
  Algorithms (SODA)}} 

@InProceedings{BKV04,
  author =       {C. Brito and E. Koutsoupias and S. Vaya},
  title =        {Competitive analysis of organization networks or multicast
acknowledgement: how much to wait?}, 
  booktitle =    SODA04,
  page =         {627--635},
  year =         2004,
  month =        {11--14 } # jan,
  address =      {New Orleans, Louisiana, USA},
}