The seat reservation problem

作     者：Boyar, J Larsen, KS 

作者机构：Odense Univ Dept Math & Comp Sci DK-5230 Odense M Denmark 

出 版 物：《ALGORITHMICA》 (算法)

年 卷 期：1999年第25卷第4期

页      面：403-417页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：on-line algorithms competitive ratio accommodating ratio graph coloring interval graphs seat reservation problem 

摘      要：We investigate the problem of giving seat reservations on-line. We assume that a train travels from a start station to an end station, stopping at k stations, including the first and last. Reservations can be made for any trip going from any station to any later station. The train has a fixed number of seats. The seat reservation system attempts to maximize income. We consider the case in which all tickets have the same price and the case in which the price of a ticket is proportional to the length of the trip. For both cases we prove upper and lower bounds of Theta (1/k) on the competitive ratio of any fair deterministic algorithm. We also define the accommodating ratio which is similar to the competitive ratio except that the only sequences of requests allowed are sequences for which the optimal off-line algorithm could accommodate all requests. We prove upper and lower bounds of Theta (1) on the accommodating ratio of any fair deterministic algorithm, in the case in which all tickets have the same price, but Theta (1/k) in the case in which the ticket price is proportional to the length of the trip. The most surprising of these results is that all fair algorithms are at least 1/2-accommodating when all tickets have the same price. We prove similar results bounding the performance of any fair randomized algorithm against an adaptive on-line adversary. We also consider concrete algorithms;more specifically, First-Fit and Best-Fit.