Title :
The parking permit problem
Author_Institution :
California Univ., Los Angeles, CA, USA
Abstract :
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.
Keywords :
competitive algorithms; marketing; purchasing; rental; trees (mathematics); online-competitive algorithm; parking permit problem; purchasing; ski rental problem; steiner forest edges; Assembly; Costs; Drives; Frequency; Network servers; Pricing; Telecommunication traffic; Traffic control; Web and internet services; Web server;
Conference_Titel :
Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on
Print_ISBN :
0-7695-2468-0
DOI :
10.1109/SFCS.2005.72
