| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2013-12-21 11:00 劣線形時間ケーキ分割アルゴリズム ○上田孝弘（京大）・伊藤大雄（電通大）  COMP2013-51 |
|
| 抄録 | （和） | 本論文では、劣線形時間で動作するケーキ分割アルゴリズムについて述べる。ケーキ分割問題とは異なる価値観を持つn人のプレイヤーが、全員が満足するように一つのケーキを分ける問題である。「満足」の基準には単純公平や無羨望などの定義があるが、本稿では全員が自分の物差しで全体の1/n以上の価値を得れば満足するという単純公平分割について論じる。単純公平分割のアルゴリズムの計算時間は決定性、乱択の両者においてΘ(n log n)時間であることが知られている。しかし、最初の一人だけに分割する場合でもo(n)-時間で動作するアルゴリズムは知られていない。我々はこれに対してケーキ分割を劣線形時間、すなわちo(n)時間で行うため枠組みを構築し、アルゴリズムを与える。具体的には、r ≦ ϵn/127人に対してO(r/ϵ)時間でケーキを分割するϵn-犠牲(ϵn-victime)アルゴリズムを与える。ただし、ϵn-犠牲とは、n 人のプレイヤーのうちのϵn 人は満足しなくても良い（犠牲）とするものである（ϵ > 0 は任意の定数とする）。なお、最初にケーキを与えられたr人は全員満足していなければならないものとする。 このアルゴリズムは、最初のr = o(n) 人に対しては劣線形時間でケーキを分割する。そして次に、ϵn-犠牲を拡張して犠牲の人数の最大値をϵn ではなくf(n) としたときのアルゴリズムを示す。 |
| （英） | In this research, we show sub-linear time algorithms for the cake-cutting problem. The cake-cutting problem is a problem of dividing a cake into pieces and handing them down to players who have different measures of the value of the cake, and then they must be “satisfied”. Though the definition of “satisfaction” are various, e.g. simple-fair, envy-free and so on, we talk about simple-fair division, i. e., each player must have 1/n value in his/her piece of cake in his/her own value function. It is known that the query complexity for the cake-cutting problem is Θ(n log n) for both deterministic and random algorithms. But no o(n)-time algorithm have been knows for dividing a piece only for the first player. We construct a framework to solve the cake-cutting problem in sublinear-time, and show algorithms in this framework. In particular, algorithms with ϵn-victims for dividing a cake for r = o(n) players in O(r/ϵ) times. And then the first r players who are assigned a piece of cake must be satisfied. Furthermore, we extend this algorithm to general f(n)-victims. | |
| キーワード | （和） | ケーキ分割問題 / 単純公平分割 / 劣線形時間 / 犠牲 / / / / |
| （英） | Cake Cutting Problem / simple-fair devision / sub-linear time algorithms / victims / / / / | |
| 文献情報 | 信学技報, vol. 113, no. 371, COMP2013-51, pp. 73-79, 2013年12月. | |
| 資料番号 | COMP2013-51 | |
| 発行日 | 2013-12-13 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2013-51 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2013-12-20 - 2013-12-21 |
| 開催地（和） | 沖縄産業支援センター |
| 開催地（英） | Okinawa Industry Support Center |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2013-12-COMP |
| 本文の言語 | 日本語 |
| タイトル（和） | 劣線形時間ケーキ分割アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | Sublinear-time cake-cutting algorithms |
| サブタイトル（英） | |
| キーワード(1)（和/英） | ケーキ分割問題 / Cake Cutting Problem |
| キーワード(2)（和/英） | 単純公平分割 / simple-fair devision |
| キーワード(3)（和/英） | 劣線形時間 / sub-linear time algorithms |
| キーワード(4)（和/英） | 犠牲 / victims |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 上田 孝弘 / Takahiro Ueda / ウエダ タカヒロ |
| 第1著者 所属（和/英） | 京都大学 (略称： 京大) Kyoto Univerisity (略称： Kyoto Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 伊藤 大雄 / Hiro Ito / イトウ ヒロオ |
| 第2著者 所属（和/英） | 電気通信大学 (略称： 電通大) The Univeristy of Electro-Communications (略称： Univ. of Electro-Comm.) |
| 講演者 | 第1著者 |
| 発表日時 | 2013-12-21 11:00:00 |
| 発表時間 | 25分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2013-51 |
| 巻番号（vol） | vol.113 |
| 号番号（no） | no.371 |
| ページ範囲 | pp.73-79 |
| ページ数 | 7 |
| 発行日 | 2013-12-13 (COMP) |
[研究会発表申込システムのトップページに戻る]