Startseite > Publikationen > Publikationen


Kling, Peter;Meyer auf der Heide, Friedhelm;Pietrzyk, Peter:

An Algorithm for Online Facility Leasing.

In: Proceedings of the 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Lecture Notes in Computer Science, Band 7355 , S. 61--72, 30. Jun. - 2. Jul. 2012, Springer


We consider an online facility location problem where clients arrive over time and their demands have to be served by opening facilities and assigning the clients to opened facilities. When opening a facility we must choose one of K different lease types to use. A lease type k has a certain lease length l k . Opening a facility i using lease type k causes a cost of and ensures that i is open for the next l k time steps. In addition to costs for opening facilities, we have to take connection costs c ij into account when assigning a client j to facility i . We develop and analyze the first online algorithm for this problem that has a time-independent competitive factor. This variant of the online facility location problem was introduced by [7] and is strongly related to both the online facility problem by [5] and the parking permit problem by [6]. Nagarajan and Williamson gave a 3-approximation algorithm for the offline problem and an O ( K log n )-competitive algorithm for the online variant. Here, n denotes the total number of clients arriving over time. We extend their result by removing the dependency on n (and thereby on the time). In general, our algorithm is -competitive. Here denotes the maximum lease length. Moreover, we prove that it is -competitive for many “natural” cases. Such cases include, for example, situations where the number of clients arriving in each time step does not vary too much, or is non-increasing, or is polynomially bounded in.


author = {Kling, Peter and Meyer auf der Heide, Friedhelm and Pietrzyk, Peter},
title = {An Algorithm for Online Facility Leasing},
booktitle = {Proceedings of the 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO)},
volume = {7355},
series = {Lecture Notes in Computer Science},
pages = {61--72},
publisher = {Springer},
month = {30~} # jun # { - 2~} # jul,
year = {2012},

BibTeX in die Zwischenablage kopieren