---
res:
bibo_abstract:
- 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 lk. Opening a facility
i using lease type k causes a cost of f k i and ensures that i is open for the
next lk time steps. In addition to costs for opening facilities, we have to take
connection costs ci j 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 Nagarajan and Williamson [7] and is strongly related to both the online facility
problem by Meyerson [5] and the parking permit problem by Meyerson [6]. Nagarajan
and Williamson gave a 3-approximation algorithm for the offline problem and an
O(Klogn)-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 O(lmax log(lmax))-competitive.
Here lmax denotes the maximum lease length. Moreover, we prove that it is O(log2(lmax))-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 lmax.
bibo_authorlist:
- foaf_Person:
foaf_givenName: Friedhelm
foaf_name: Meyer auf der Heide, Friedhelm
foaf_surname: Meyer auf der Heide
foaf_workInfoHomepage: http://www.librecat.org/personId=15523
- foaf_Person:
foaf_givenName: Peter
foaf_name: Pietrzyk, Peter
foaf_surname: Pietrzyk
- foaf_Person:
foaf_givenName: Peter
foaf_name: Kling, Peter
foaf_surname: Kling
bibo_doi: 10.1007/978-3-642-31104-8_6
dct_date: 2012^xs_gYear
dct_title: An Algorithm for Facility Leasing@
...