Paper Info
Title
Offline and online facility leasing
Abstract
We study the problem of leasing facilities over time, following the general infrastructure leasing problem framework introduced by Anthony and Gupta [1]. If there are K different lease types, Anthony and Gupta give an O(K)-approximation algorithm for the problem. We are able to improve this to a 3-approximation algorithm by using a variant of the primal-dual facility location algorithm of Jain and Vazirani [5]. We also consider the online version of the facility leasing problem, in which the clients to be served arrive over time and are not known in advance. This problem generalizes both the online facility location problem (introduced by Meyerson [6]) and the parking permit problem (also introduced by Meyerson [7]). We give a deterministic algorithm for the problem that is O(K log n)-competitive. To achieve our result, we modify an O(log n)-competitive algorithm of Fotakis [2] for the online facility location problem.
Year
DOI
Venue
2008
10.1007/978-3-540-68891-4_21
IPCO
Keywords
Field
DocType
online facility location problem,facility leasing problem,general infrastructure leasing problem,parking permit problem,problem generalizes,3-approximation algorithm,approximation algorithm,competitive algorithm,deterministic algorithm,primal-dual facility location algorithm,online facility leasing
Binary logarithm,Mathematical optimization,Computer science,Facility location problem,Competitive algorithm,Deterministic algorithm,1-center problem,Competitive analysis
Conference
Volume
Issue
ISSN
10
4
1572-5286
ISBN
Citations 
PageRank 
3-540-68886-2
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
Chandrashekhar Nagarajan11517.62
David P. Williamson23564413.34