Random-Order Models

Anupam Gupta, Sahil Singla

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

This chapter introduces the random-order model in online algorithms. In this model, the input is chosen by an adversary, then randomly permuted before being presented to the algorithm. This reshuffling often weakens the power of the adversary and allows for improved algorithmic guarantees. We show such improvements for two broad classes of problems: packing problems where we must pick a constrained set of items to maximize total value, and covering problems where we must satisfy given requirements at minimum total cost.We also discuss how random-order model relates to other stochastic models used for non-worst-case competitive analysis.

Original languageEnglish (US)
Title of host publicationBeyond the Worst-Case Analysis of Algorithms
PublisherCambridge University Press
Pages234-258
Number of pages25
ISBN (Electronic)9781108637435
ISBN (Print)9781108494311
DOIs
StatePublished - Jan 1 2021

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics

Fingerprint

Dive into the research topics of 'Random-Order Models'. Together they form a unique fingerprint.

Cite this