ダウンロード数: 31
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
j.tcs.2021.03.037.pdf | 752.62 kB | Adobe PDF | 見る/開く |
完全メタデータレコード
DCフィールド | 値 | 言語 |
---|---|---|
dc.contributor.author | Ito, Takehiro | en |
dc.contributor.author | Kamiyama, Naoyuki | en |
dc.contributor.author | Kobayashi, Yusuke | en |
dc.contributor.author | Okamoto, Yoshio | en |
dc.contributor.alternative | 小林, 佑輔 | ja |
dc.date.accessioned | 2022-03-03T09:22:20Z | - |
dc.date.available | 2022-03-03T09:22:20Z | - |
dc.date.issued | 2021-05 | - |
dc.identifier.uri | http://hdl.handle.net/2433/268289 | - |
dc.description.abstract | We initiate the systematic algorithmic study for gerrymandering over graphs that was recently introduced by Cohen-Zemach, Lewenberg and Rosenschein. Namely, we study a strategic procedure for a political districting designer to draw electoral district boundaries so that a particular target candidate can win in an election. We focus on the existence of such a strategy under the plurality voting rule, and give interesting contrasts which classify easy and hard instances with respect to polynomial-time solvability. For example, we prove that the problem for trees is strongly NP-complete (thus unlikely to have a pseudo-polynomial-time algorithm), but has a pseudo-polynomial-time algorithm when the number of candidates is constant. Another example is to prove that the problem for complete graphs is NP-complete when the number of electoral districts is two, while is solvable in polynomial time when it is more than two. | en |
dc.language.iso | eng | - |
dc.publisher | Elsevier BV | en |
dc.rights | © 2021. This manuscript version is made available under the Creative Commons Attribution-NonCommercial-NoDerivs 4.0 license. | en |
dc.rights | The full-text file will be made open to the public on 08 May 2023 in accordance with publisher's 'Terms and Conditions for Self-Archiving'. | en |
dc.rights | This is not the published version. Please cite only the published version. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 | en |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | - |
dc.subject | Gerrymandering | en |
dc.subject | Computational social choice | en |
dc.subject | Graph algorithms | en |
dc.title | Algorithms for gerrymandering over graphs | en |
dc.type | journal article | - |
dc.type.niitype | Journal Article | - |
dc.identifier.jtitle | Theoretical Computer Science | en |
dc.identifier.volume | 868 | - |
dc.identifier.spage | 30 | - |
dc.identifier.epage | 45 | - |
dc.relation.doi | 10.1016/j.tcs.2021.03.037 | - |
dc.textversion | author | - |
dcterms.accessRights | open access | - |
datacite.date.available | 2023-05-08 | - |
datacite.awardNumber | 16K00004 | - |
datacite.awardNumber | 18H04091 | - |
datacite.awardNumber | 19K11814 | - |
datacite.awardNumber | 20H05793 | - |
datacite.awardNumber | 16K16010 | - |
datacite.awardNumber | 18H05291 | - |
datacite.awardNumber | 19H05485 | - |
datacite.awardNumber | 20K11692 | - |
datacite.awardNumber | 20H05795 | - |
datacite.awardNumber | 15K00009 | - |
datacite.awardNumber | 20K11670 | - |
datacite.awardNumber | 20H05795 | - |
datacite.awardNumber.uri | https://kaken.nii.ac.jp/ja/grant/KAKENHI-PROJECT-16K00004/ | - |
datacite.awardNumber.uri | https://kaken.nii.ac.jp/ja/grant/KAKENHI-PROJECT-18H04091/ | - |
datacite.awardNumber.uri | https://kaken.nii.ac.jp/ja/grant/KAKENHI-PROJECT-19K11814/ | - |
datacite.awardNumber.uri | https://kaken.nii.ac.jp/ja/grant/KAKENHI-PLANNED-20H05793/ | - |
datacite.awardNumber.uri | https://kaken.nii.ac.jp/ja/grant/KAKENHI-PROJECT-16K16010/ | - |
datacite.awardNumber.uri | https://kaken.nii.ac.jp/ja/grant/KAKENHI-PROJECT-18H05291/ | - |
datacite.awardNumber.uri | https://kaken.nii.ac.jp/ja/grant/KAKENHI-PROJECT-20K20417/ | - |
datacite.awardNumber.uri | https://kaken.nii.ac.jp/ja/grant/KAKENHI-PROJECT-20K11692/ | - |
datacite.awardNumber.uri | https://kaken.nii.ac.jp/ja/grant/KAKENHI-PLANNED-20H05795/ | - |
datacite.awardNumber.uri | https://kaken.nii.ac.jp/ja/grant/KAKENHI-PROJECT-15K00009/ | - |
datacite.awardNumber.uri | https://kaken.nii.ac.jp/ja/grant/KAKENHI-PROJECT-20K11670/ | - |
datacite.awardNumber.uri | https://kaken.nii.ac.jp/ja/grant/KAKENHI-PLANNED-20H05795/ | - |
dc.identifier.pissn | 0304-3975 | - |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.awardTitle | 不満度を最小化する運搬経路問題に対するグラフアルゴリズム手法とその一般化 | ja |
jpcoar.awardTitle | 理論的に困難な問題を現実的な時間で解くアルゴリズムとデータ構造の研究 | ja |
jpcoar.awardTitle | 迂回の特性を捉えた最短遷移アルゴリズムに関する研究 | ja |
jpcoar.awardTitle | 計算機科学アプローチによる組合せ遷移の展開 : アルゴリズムの自動生成に向けて | ja |
jpcoar.awardTitle | 頑健なネットワークの設計に向けた組合せ最適化理論の研究 | ja |
jpcoar.awardTitle | 巨大グラフとビッグデータ解析の基礎基盤:理論研究と高速アルゴリズム開発 | ja |
jpcoar.awardTitle | 走行税課金による道路インフラ維持管理 --EV化と車両認証のデジタル時代を迎えて-- | ja |
jpcoar.awardTitle | 組合せ最適化における多面体手法の高度化 | ja |
jpcoar.awardTitle | 数学アプローチによる組合せ遷移の展開:活用事例を手がかりとして新解法へ | ja |
jpcoar.awardTitle | 計算幾何学と計算トポロジーが拓く新時代データ解析の理論基盤 | ja |
jpcoar.awardTitle | 大規模配位空間の最適化理論:離散構造論の視点を中心にして | ja |
jpcoar.awardTitle | 数学アプローチによる組合せ遷移の展開:活用事例を手がかりとして新解法へ | ja |
出現コレクション: | 学術雑誌掲載論文等 |
![](/dspace/image/articlelinker.gif)
このアイテムは次のライセンスが設定されています: クリエイティブ・コモンズ・ライセンス