Paper Info
Title
Competitive Algorithms for Cottage Rental
Abstract
Suppose that you are given a pool of cottages which you have for rent for a given holiday period. People make reservation requests over the phone, requesting a cottage from some time aj to bj. Given a rental request one must decide without (complete) knowledge about future requests, whether to accept this request and make a profit that is proportional to the renting duration bj−aj or to reject it. This problem is related to the seat-reservation problem (see e.g. [J. Boyar, K.S. Larsen, The seat reservation problem, Algorithmica 25 (1999) 403–417, J. Boyar, S. Krarup, M.N. Nielsen, Seat reservation allowing seat changes, Journal of Algorithms 52 (2004) 169–192]), the difference being that the specific cottage need not be fixed upon acceptance of a request. Moreover, in [J. Boyar, K.S. Larsen, The seat reservation problem, Algorithmica 25 (1999) 403–417, J. Boyar, S. Krarup, M.N. Nielsen, Seat reservation allowing seat changes, Journal of Algorithms 52 (2004) 169–192] there is a fairness restriction: it is assumed that passengers that can be accepted must be accepted. Anyone trying to reserve a cottage for one night in the middle of the high season will find out that cottage owners are not necessarily fair (in this sense).
Year
DOI
Venue
2006
10.1016/j.endm.2006.06.069
Electronic Notes in Discrete Mathematics
Keywords
Field
DocType
Competitive analysis,Online Algorithms,Scheduling
Reservation,Randomized algorithm,Online algorithm,Scheduling (computing),Algorithm,Operations research,Phone,Adversary,Mathematics,Competitive analysis,Renting
Journal
Volume
ISSN
Citations 
25
1571-0653
0
PageRank 
References 
Authors
0.34
2
3
Name
Order
Citations
PageRank
Stephan Westphal19713.41
Sven O. Krumke230836.62
van stee349039.87