Online constrained forest and prize-collecting network design

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.