|
|
湖南科技大学学报(自然科学版) 2013
简单规则下VoteControl问题的复杂性分析Keywords: VoteControl问题,复杂性,得分规则 Abstract: 给定候选人集合C,投票集合V=(v1,v2,…,vn)和候选人c∈C,是否存在V的子集V′,|V′|≤k,使得c∈r(V＼V′).该问题在不同的得分规则下复杂性是不同的.在plurality规则的基础上证明了Reto规则下VoteControl问题是多项式时间可解的,并给出了k′-approval规则下该问题是NP-Complete的证明.
|
