Online And Offline Facility Location And Network Design

Abstract

We study a few online and offline facility location and network design problems, including an offline facility location model with submodular opening costs, an online prize-collecting facility location model, an offline singledemand capacitated facility location model and an online prize-collecting Steiner tree problem. In this thesis, we present algorithms for these problems and their approximation ratio or competitive ratio analysis.