In this work we study online problems from the facility lo cation and Steiner families,
through the p oint of view of comp etitive analysis. The goal in these problems is to build
a minimum cost network to attend a certain demand. We present known results for the
Online Facility Lo cation problem (OFL), the Online Steiner Tree problem (OST) and
the Online Single-Source Rent-or-Buy problem (OSRoB). The OFL consists of serving a set
of clients by opening some facilities and by connecting each client to a facility. The OST
aims to connect a set of terminals in order to create a tree network, that may contain
nonterminals, called Steiner no des. The OSRoB is a rent-or-buy version of the OST, in
which all terminals must b e connected to a sp ecial no de called ro ot. The algorithms and
techniques that we present for these problems play an imp ortant role in the design of our
algorithms for the problems we consider.
We present new results for the Online Prize-Collecting Facility Lo cation problem (OPFL),
the Online Steiner Tree Star problem (OSTS), and the Online Connected Facility
Location problem (OCFL). The OPFL is a generalization of the OFL, in which some
clients may b e left unconnected by paying a p enalty. The OSTS is a variant of the OST,
in which the no des have non-negative costs. The OCFL is a combination of the OFL
and the OST, in which a set of clients needs to b e served by opening some facilities, by
connecting each client to a facility, and by creating a more exp ensive tree network that
connects the open facilities.