Parameterized Algorithmics for Computational Social Choice:Nine Research Challenges

作     者：Robert Bredereck Jiehua Chen Piotr Faliszewski Jiong Guo Rolf Niedermeier Gerhard J.Woeginger 

作者机构：the Institut fr Softwaretechnik und Theoretische InformatikTU Berlin Berlin Germany AGH University of Science and Technology Kraków Poland the Cluster of Excellence Multimodal Computing and InteractionUniversitt des SaarlandesSaarbrcken Germany the Department of Mathematics and Computer Science TU Eindhoven Eindhoven The Netherlands 

出 版 物：《Tsinghua Science and Technology》 (清华大学学报（自然科学版（英文版）)

年 卷 期：2014年第19卷第4期

页      面：358-373页

核心收录：

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：supported by the Deutsche Forschungsgemeinschaft, project PAWS (NI 369/10) supported by the Studienstiftung des Deutschen Volkes supported by DFG "Cluster of Excellence Multimodal Computing and Interaction" supported by DIAMANT (a mathematics cluster of the Netherlands Organization for Scientific Research NWO) the Alexander von Humboldt Foundation, Bonn, Germany 

主　　题：NP hard problems parameterized complexity fixed parameter tractability kernelization exact algorithms voting decision making cake cutting 

摘      要：Computational Social Choice is an interdisciplinary research area involving Economics, Political Science,and Social Science on the one side, and Mathematics and Computer Science（including Artificial Intelligence and Multiagent Systems） on the other side. Typical computational problems studied in this field include the vulnerability of voting procedures against attacks, or preference aggregation in multi-agent systems. Parameterized Algorithmics is a subfield of Theoretical Computer Science seeking to exploit meaningful problem-specific parameters in order to identify tractable special cases of in general computationally hard problems. In this paper, we propose nine of our favorite research challenges concerning the parameterized complexity of problems appearing in this context. This work is dedicated to Jianer Chen, one of the strongest problem solvers in the history of parameterized algorithmics,on the occasion of his 60 th birthday.