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

概要

論文の詳細を見る
座席予約問題では駅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)に改良した.
2010-11-26