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

• Material Type: 記事
• Title: 座席予約問題における競合比の上下限の改良
• Author/Editor: 岡本, 和也; 宮崎, 修一
• Publication, Distribution, etc.: 電子情報通信学会
• Publication Date: 2010-11-26
• Publication Date (W3CDTF): 2010
• Alternative Title: Improving the Competitive Ratios of the Seat Reservation Problem
• Periodical title: 信学技報
• No. or year of volume/issue: 110 325
• Volume: 110
• Issue: 325
• Pages: 45-51
• ISSN (Periodical Title): ISSN : 0913-5685; PISSN : 0913-5685; EISSN : 2432-6380
• Subject Heading: 座席予約問題問題; オンライン問題; オンラインアルゴリズム; 競合比解析; the seat reservation problem; online problem; online algorithms; competitive analysis
• Target Audience: 一般
• Note (General): 出版タイプ： VoR; <コンピュテーション研究会(COMP)> 2010年12月 3日(金) 10:30 - 17:10, 九州工業大学 Kyutechプラザ
• Format (IMT): application/pdf
• Source: IEICE_tec.rep_COMP2010-45.pdf （fulltext）; http://repository.kulib.kyoto-u.ac.jp/dspace/bitstream/2433/227007/1/IEICE_tec.rep_COMP2010-45.pdf
• Access Restrictions: インターネット公開
• Periodical Title (NCID): AN10013152; https://ci.nii.ac.jp/ncid/AN10013152
• Data Provider (Database): 国立情報学研究所 : 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）; https://irdb.nii.ac.jp
• Original Data Provider (Database): 京都大学 : 京都大学学術情報リポジトリ

• Summary, etc.: 座席予約問題では駅s_1から駅s_kまでのk駅に停まるn席の座席を持った列車を考える.各乗客は出発駅s_iから到着駅s_j(1≦i≦j≦k)までのチケットを要求する.オンラインアルゴリズムは, 未来の要求を知らずに各乗客をn席の座席の1つに割り当てる必要がある.座席予約問題の目的はチケットの売上合計...