Name
Abstract | ||
|---|---|---|
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]. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.endm.2015.07.026 | Electronic Notes in Discrete Mathematics |
Keywords | DocType | Volume |
Online Algorithms,Competitive Analysis,Prize-Collecting Facility Location Problem,Primal-Dual Method | Journal | 50 |
ISSN | Citations | PageRank |
1571-0653 | 1 | 0.37 |
References | Authors | |
5 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mário César San Felice | 1 | 4 | 2.13 |
| Sin-Shuen Cheung | 2 | 8 | 1.27 |
| Orlando Lee | 3 | 6 | 1.85 |
| David P. Williamson | 4 | 3564 | 413.34 |