The Online Prize-Collecting Facility Location Problem

In this paper we propose the Online Prize-Collecting Facility Location problem (OPCFL), which is an online version of the Prize-Collecting Facility Location problem (PCFL). The PCFL is a generalization of the Uncapacitated Facility Location problem (FL) in which some clients may be left unconnected by paying a penalty. Another way to think about it is that every client has a prize that can only be collected if it is connected. We give a primal-dual O(log n)-competitive algorithm for the OPCFL based on previous algorithms for Online Facility Location (OFL) due to Fotakis [Fotakis, D., A primal-dual algorithm for online non-uniform facility location, Journal of Discrete Algorithms 5 (2007), pp. 141–148] and Nagarajan and Williamson [Nagarajan, C. and D. P. Williamson, Offline and online facility leasing, Discrete Optimization 10 (2013), pp. 361–370].