Access count of this item: 98

Files in This Item:
File Description SizeFormat 
IEICE_tec.rep_COMP2010-45.pdf2.56 MBAdobe PDFView/Open
Title: 座席予約問題における競合比の上下限の改良
Other Titles: Improving the Competitive Ratios of the Seat Reservation Problem
Authors: 岡本, 和也  KAKEN_name
宮崎, 修一  kyouindb  KAKEN_id
Author's alias: Okamoto, Kazuya
Miyazaki, Shuichi
Keywords: 座席予約問題問題
オンライン問題
オンラインアルゴリズム
競合比解析
the seat reservation problem
online problem
online algorithms
competitive analysis
Issue Date: 26-Nov-2010
Publisher: 電子情報通信学会
Journal title: 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報
Volume: 110
Issue: 325
Start page: 45
End page: 51
Thesis number: COMP2010-45
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.
Description: <コンピュテーション研究会(COMP)> 2010年12月 3日(金) 10:30 - 17:10, 九州工業大学 Kyutechプラザ
Rights: © 2010 by IEICE
URI: http://hdl.handle.net/2433/227007
Related Link: http://www.ieice.org/ken/paper/20101203m0Du/
Appears in Collections:Journal Articles

Show full item record

Export to RefWorks


Export Format: 


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.