loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05)
The Parking Permit Problem
Pittsburgh, Pennsylvania, USA
October 23-October 25
ISBN: 0-7695-2468-0
ASCII Text
x 
 
Adam Meyerson Meyerson, "The Parking Permit Problem," Foundations of Computer Science, Annual IEEE Symposium on, pp. 274-284, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), 2005.
 
 
BibTex
x
 
@article{ 10.1109/SFCS.2005.72,
author = {Adam Meyerson Meyerson},
title = {The Parking Permit Problem},
journal ={Foundations of Computer Science, Annual IEEE Symposium on},
volume = {0},
year = {2005},
isbn = {0-7695-2468-0},
pages = {274-284},
doi = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.72},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Foundations of Computer Science, Annual IEEE Symposium on
TI - The Parking Permit Problem
SN - 0-7695-2468-0
SP274
EP284
A1 - Adam Meyerson Meyerson,
PY - 2005
KW - null
VL - 0
JA - Foundations of Computer Science, Annual IEEE Symposium on
ER -
 
Adam Meyerson Meyerson, University of California, Los Angeles

We consider online problems where purchases have time durations which expire regardless of whether the purchase is used or not. The Parking Permit Problem is the natural analog of the well-studied ski rental problem in this model, and we provide matching upper and lower bounds on the competitive ratio for this problem. By extending the techniques thus developed, we give an online-competitive algorithm for the problem of renting steiner forest edges with time durations.

Citation:
Adam Meyerson Meyerson, "The Parking Permit Problem," focs, pp.274-284, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), 2005
Usage of this product signifies your acceptance of the Terms of Use.