We study the parameterized complexity of Winners Determination for three prevalent $k$-committee selection rules, namely the minimax approval voting (MAV), the proportional approval voting (PAV), and the Chamberlin-Courant's approval voting (CCAV). It is known that Winners Determination for these rules is NP-hard. Moreover, these problems have been studied from the parameterized complexity point of view with respect to some natural parameters recently. However, many results turned out to be W[1]-hard or W[2]-hard. Aiming at deriving more fixed-parameter algorithms, we revisit these problems by considering more natural and important single parameters, combined parameters, and structural parameters.
翻译：我们研究了三个通用的美元委员会甄选规则,即小额核准投票(MAV)、比例核准投票(PAV)和Camberlin-Courant的核准投票(CCAV)的 " 赢家决定 " 的参数复杂性。众所周知,这些规则的 " 赢家决定 " 是硬的。此外,这些问题是从最近一些自然参数参数的参数化复杂点来研究的。然而,许多结果是W[1]硬的或W[2]硬的。为了得出更多的固定参数算法,我们通过考虑更自然和重要的单一参数、综合参数和结构参数来重新审视这些问题。
相关内容
微信扫码咨询专知VIP会员