座席予約問題における競合比の上下限の改良

Abstract

座席予約問題では駅s_1から駅s_kまでのk駅に停まるn席の座席を持った列車を考える.各乗客は出発駅s_iから到着駅s_j(1≦i≦j≦k)までのチケットを要求する.オンラインアルゴリズムは, 未来の要求を知らずに各乗客をn席の座席の1つに割り当てる必要がある.座席予約問題の目的はチケットの売上合計額を最大化することである.チケットの価格設定により, 座席予約問題には2つのモデルがある.一つは単一価格問題であり, もう一つは比例価格問題である.我々は, 両方のモデルにおいて, 競合比の上下限を改良した.単一価格問題に関しては, 上限を8/(k+5)から4/(k-2√<k-1>+4)に改良した.また, Worst-Fitアルゴリズムの上限も4/(k-1)から2/(k-2√<k-1>+2)に改良した.さらに, 比例価格問題に関しては, 上限を(4+2√<13>)/(k+3+2√<13>)((≃11.2/(k+10.2))から(3+√<13>)/(k-1+√<13>)((≃6.6/(k+2.6))に改良し, 下限を1/(k-1)から2/(k-1)に改良した.

In the seat reservation problem, there are k station, 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 spacifying 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-2√<k-1>+4), which improves the previous bound of 8/(k+5). We also give an upper bound of 2/(k-2√<k-1>+2) for the competitive ratio of Worst-Fit algorithm, which improves the previous bound of 4/(k-1). For the proportional price problem, we give upper and lower bounds of (3+√<13>)/(k-1+√<13>)((≃6.6/(k+2.6)) and 2/(k-1), respectively, on the competitive ratio, which improves the previous bounds of (4+2√<13>)/(k+3+2√<13>)((≃11.2/(k+10.2)) and 1/(k-1), respectively.