文献

J-GLOBAL ID：201902267954674492   整理番号：19A1661342

高多重度選挙問題【JST・京大機械翻訳】

High-multiplicity election problems

著者 (2件)： Fitzsimmons Zack (Department of Mathematics and Computer Science, College of the Holy Cross, Worcester, MA, USA) ,  Hemaspaandra Edith (Department of Computer Science, Rochester Institute of Technology, Rochester, NY, USA)
資料名： Autonomous Agents and Multi-Agent Systems  (Autonomous Agents and Multi-Agent Systems)
巻： 33  号： 4  ページ： 383-402  発行年： 2019年 
JST資料番号： W1340A  ISSN： 1387-2532  CODEN： AAMSFJ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 選択の計算研究は,一般的に,エレクトレートの選好が投票のリストとして生じると仮定している。文脈に依存して,エレクトレートの明確な投票とそれらのカウント,すなわち高い多重性表現として,リストを簡潔に表現することはより自然であるかもしれない。この表現が選択問題の複雑さにどのように影響するかを考察した。高多重度表現は標準表現よりも指数関数的に小さい可能性があり,標準表現における選択問題に対する多くの多項式時間アルゴリズムは指数関数的時間になる。驚くべきことに,多項式時間選択問題に対して,著者らはしばしば同じアプローチを適応することができるか,または新しいアルゴリズムを提供することができて,これらの問題が高い多重性ケースにおいて多項式時間のままであることを示した。これは,各投票者が重みを持ち,複雑さが通常増加する場合とは対照的である。このプロセスでは,高多重度スケジューリングと高多重度選択の操作の間の関係を調べた。そして,任意のジョブ長さの固定集合に対して,一様な並列マシン上での高い多重度スケジューリングが,以前に2つのジョブ長だけで知られていたPにあることを示した。著者らは,多項式時間選択問題が,高い多重度表現に移動するとき,Pにおいて残らない自然の事例を見つけなかった。しかし,複雑さが増加する一つの自然NP困難選択問題,すなわち,Kemeny選択のための勝者決定を見出した。Copyright 2019 Springer Science+Business Media, LLC, part of Springer Nature Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *多重度 ,  並列計算機 ,  選択問題 ,  投票 ,  NP困難 ,  アルゴリズム ,  CASE ,  スケジューリング ,  指数関数
準シソーラス用語： 多項式時間 ,  多項式時間アルゴリズム ,  *選挙 , 【Automatic Indexing@JST】

著者キーワード (5件)： 計算社会選択 ,  選挙 ,  操作行動 ,  高多重度表現 ,  スケジューリング

分類 (1件)： 人工知能  (JE08000Z)

タイトルに関連する用語 (2件)： 多重度 ,  選挙