著者

岡本 和也 宮崎 修一

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.110, no.325, pp.45-51, 2010-11-26

---

座席予約問題では駅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>)((&sime;11.2/(k+10.2))から(3+√<13>)/(k-1+√<13>)((&sime;6.6/(k+2.6))に改良し,下限を1/(k-1)から2/(k-1)に改良した.