| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [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著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2010-12-03 16:00:00 |
| 発表時間 | 35分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2010-45 |
| 巻番号（vol） | vol.110 |
| 号番号（no） | no.325 |
| ページ範囲 | pp.45-51 |
| ページ数 | 7 |
| 発行日 | 2010-11-26 (COMP) |
[研究会発表申込システムのトップページに戻る]