Improving the Competitive Ratios of the Seat Reservation Problem

摘要

In the seat reservation problem, there are k stations, s_1 through s_k, and one train with n seats departing from the station s_1 and arriving at the station s_k- Each passenger orders a ticket from station s_i to station s_j (1 ≤ i ≤ j ≤ k) by specifying i and j. The task of an online algorithm is to assign one of n seats to each passenger online, i.e., without knowing future requests. The purpose of the problem is to maximize the total price of the sold tickets. There are two models, the unit price problem and the proportional price problem, depending on the pricing policy of tickets. In this paper, we improve upper and lower bounds on the competitive ratios for both models: For the unit price problem, we give an upper bound of 4/k-2k-1+4~(1//2) which improves thernprevious bound of 8/k+5. We also give an upper bound of 2/k-2 k-1+2~(1/2)rnthe competitive ratio of Worst-Fit algorithm, which improves the previous bound of 4/k-1. For the proportional price problem, we give upper andrnlower bounds of 3+13~(1/2)/k-1+13~(1/2) (approx=6.6/k+2.6) and 2/k-1,respectively, on the competitive ratio, which improves the previous bounds of 4+2 13~(1/2)/k+3+2 13~(1/2)(approx=11.2/k+10.2) and 1/k-1, respectively.