お知らせ ◆電子情報通信学会における研究会開催について(新型コロナウイルス関連)
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
技報オンライン
‥‥ (ESS/通ソ/エレソ/ISS)
技報アーカイブ
‥‥ (エレソ/通ソ)
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2010-12-03 16:00
座席予約問題における競合比の上下限の改良
岡本和也宮崎修一京大COMP2010-45
抄録 (和) 座席予約問題では駅$s_{1}$から駅$s_{k}$までの$k$駅に停まる$n$席の
座席を持った列車を考える.各乗客は出発駅$s_{i}$から
到着駅$s_{j}$($1 \leq i < j\leq k$)までのチケットを要求する.
オンラインアルゴリズムは,未来の要求を知らずに各乗客を$n$席の座席の1つに
割り当てる必要がある.座席予約問題の目的はチケットの売上合計額を
最大化することである.チケットの価格設定により,座席予約問題には
2つのモデルがある.一つは単一価格問題であり,もう一つは比例価格問題である.
我々は,両方のモデルにおいて,競合比の上下限を改良した.
単一価格問題に関しては,上限を$\frac{8}{k+5}$から
$\frac{4}{k-2\sqrt{k-1}+4}$に改良した.また,Worst-Fitアルゴリズムの
上限も$\frac{4}{k-1}$から$\frac{2}{k-2\sqrt{k-1}+2}$に改良した.
さらに,比例価格問題に関しては,上限を
$\frac{4+2\sqrt{13}}{k+3+2\sqrt{13}} (\simeq \frac{11.2}{k+10.2})$から
$\frac{3+\sqrt{13}}{k-1+\sqrt{13}} (\simeq \frac{6.6}{k+2.6})$に改良し,
下限を$\frac{1}{k-1}$から$\frac{2}{k-1}$に改良した. 
(英) 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 \leq i < j
\leq 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 $\frac{4}{k-2\sqrt{k-1}+4}$, which
improves the previous bound of $\frac{8}{k+5}$. We also give an upper
bound of $\frac{2}{k-2\sqrt{k-1}+2}$ for the competitive ratio of
Worst-Fit algorithm, which improves the previous bound of
$\frac{4}{k-1}$. For the proportional price problem, we give upper
and lower bounds of $\frac{3+\sqrt{13}}{k-1+\sqrt{13}} (\simeq
\frac{6.6}{k+2.6})$ and $\frac{2}{k-1}$, respectively, on the
competitive ratio, which improves the previous bounds of
$\frac{4+2\sqrt{13}}{k+3+2\sqrt{13}} (\simeq \frac{11.2}{k+10.2})$ and
$\frac{1}{k-1}$, respectively.
キーワード (和) 座席予約問題問題 / オンライン問題 / オンラインアルゴリズム / 競合比解析 / / / /  
(英) the seat reservation problem / online problem / online algorithms / competitive analysis / / / /  
文献情報 信学技報, vol. 110, no. 325, COMP2010-45, pp. 45-51, 2010年12月.
資料番号 COMP2010-45 
発行日 2010-11-26 (COMP) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380
著作権に
ついて
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034)
PDFダウンロード COMP2010-45

研究会情報
研究会 COMP  
開催期間 2010-12-03 - 2010-12-03 
開催地(和) 九州工業大学 Kyutechプラザ 
開催地(英) Kyutech Plaza, Kyushu Institute of Technology 
テーマ(和)  
テーマ(英)  
講演論文情報の詳細
申込み研究会 COMP 
会議コード 2010-12-COMP 
本文の言語 日本語 
タイトル(和) 座席予約問題における競合比の上下限の改良 
サブタイトル(和)  
タイトル(英) Improving the Competitive Ratios of the Seat Reservation Problem 
サブタイトル(英)  
キーワード(1)(和/英) 座席予約問題問題 / the seat reservation problem  
キーワード(2)(和/英) オンライン問題 / online problem  
キーワード(3)(和/英) オンラインアルゴリズム / online algorithms  
キーワード(4)(和/英) 競合比解析 / competitive analysis  
キーワード(5)(和/英) /  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 岡本 和也 / Kazuya Okamoto / オカモト カズヤ
第1著者 所属(和/英) 京都大学 (略称: 京大)
Kyoto University (略称: Kyoto Univ.)
第2著者 氏名(和/英/ヨミ) 宮崎 修一 / Shuichi Miyazaki /
第2著者 所属(和/英) 京都大学 (略称: 京大)
Kyoto University (略称: Kyoto Univ.)
第3著者 氏名(和/英/ヨミ) / /
第3著者 所属(和/英) (略称: )
(略称: )
第4著者 氏名(和/英/ヨミ) / /
第4著者 所属(和/英) (略称: )
(略称: )
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2010-12-03 16:00:00 
発表時間 35 
申込先研究会 COMP 
資料番号 IEICE-COMP2010-45 
巻番号(vol) IEICE-110 
号番号(no) no.325 
ページ範囲 pp.45-51 
ページ数 IEICE-7 
発行日 IEICE-COMP-2010-11-26 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会