The online set aggregation problem

Rodrigo A. Carrasco, Kirk Pruhs, Cliff Stein, José Verschae

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

6 Scopus citations

Abstract

We introduce the online Set Aggregation Problem, which is a natural generalization of the Multi-Level Aggregation Problem, which in turn generalizes the TCP Acknowledgment Problem and the Joint Replenishment Problem. We give a deterministic online algorithm, and show that its competitive ratio is logarithmic in the number of requests. We also give a matching lower bound on the competitive ratio of any randomized online algorithm.

Original languageEnglish
Title of host publicationLATIN 2018
Subtitle of host publicationTheoretical Informatics - 13th Latin American Symposium, Proceedings
EditorsMiguel A. Mosteiro, Michael A. Bender, Martin Farach-Colton
PublisherSpringer Verlag
Pages245-259
Number of pages15
ISBN (Print)9783319774039
DOIs
StatePublished - 2018
Externally publishedYes
Event13th International Symposium on Latin American Theoretical Informatics, LATIN 2018 - Buenos Aires, Argentina
Duration: 16 Apr 201819 Apr 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10807 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference13th International Symposium on Latin American Theoretical Informatics, LATIN 2018
Country/TerritoryArgentina
CityBuenos Aires
Period16/04/1819/04/18

Keywords

  • Competitive analysis
  • Multilevel aggregation
  • Online algorithms
  • Set aggregation

Fingerprint

Dive into the research topics of 'The online set aggregation problem'. Together they form a unique fingerprint.

Cite this