Parameterized Algorithmics for Computational Social Choice:Nine Research Challenges  

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

机构地区：[1]the Institut fr Softwaretechnik und Theoretische Informatik,TU Berlin, Berlin, Germany [2]AGH University of Science and Technology, Kraków, Poland [3]the Cluster of Excellence Multimodal Computing and Interaction,Universitt des Saarlandes,Saarbrcken, Germany [4]the Department of Mathematics and Computer Science, TU Eindhoven, Eindhoven, The Netherlands

出　　处：《Tsinghua Science and Technology》2014年第4期358-373,共16页清华大学学报（自然科学版（英文版）

基　　金：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

摘　　要：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.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.

关 键 词：NP-hard problems parameterized complexity fixed-parameter tractability kernelization exact algorithms voting decision making cake cutting 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]