Online constrained forest and prize-collecting network design

J. Qian, S.W. Umboh, D.P. Williamson

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)

Abstract

In this paper, we study a very general type of online network design problem, and generalize two different previous algorithms, one for an online network design problem due to Berman and Coulston (Proceedings of the 29th annual ACM symposium on theory of computing, pp 344–353, 1997) and one for (offline) general network design problems due to Goemans and Williamson (SIAM J Comput 24:296–317, 1995); we give an O(logk)-competitive algorithm, where k is the number of nodes that must be connected. We also consider a further generalization of the problem that allows us to pay penalties in exchange for violating connectivity constraints; we give an online O(logk)-competitive algorithm for this case as well.
Original languageEnglish
Pages (from-to)3335–3364
Number of pages30
JournalAlgorithmica
Volume80
Issue number11
DOIs
Publication statusPublished - 1 Nov 2018

Keywords

  • Competitive ratio
  • Generalized Steiner tree
  • Online algorithms
  • Prize-collecting Steiner tree

Fingerprint

Dive into the research topics of 'Online constrained forest and prize-collecting network design'. Together they form a unique fingerprint.

Cite this