文章摘要
简单规则下Vote Control问题的复杂性分析
The complexity of Vote Control problem under simple rules
  
DOI:
中文关键词: Vote Control问题  复杂性  得分规则
英文关键词: Vote Control problem  complexity  scoring rule
基金项目:河南省科技攻关项目(122102310442)
作者单位
秦勤,王雪瑞,李建 河南工程学院 计算机学院,河南 郑州 450007 
摘要点击次数: 1060
全文下载次数: 137
中文摘要:
      给定候选人集合C,投票集合V=(v1,v2,…,vn)和候选人c∈C,是否存在V的子集V′,|V′|≤k,使得c∈r(V\V′).该问题在不同的得分规则下复杂性是不同的.在plurality规则的基础上证明了Reto规则下Vote Control问题是多项式时间可解的,并给出了k′-approval规则下该问题是NP-Complete的证明.
英文摘要:
      Given a set of candidatesC, a profile of partial votesV=(v1,v2,…,vn), and a distinguished candidatec∈C,is there a subset V′,|V′|≤k such that c∈r(V\V′). The complexity of this problem is different under different scoring rules. The vote control problem was proved under Reto rule can be solved in polynomial time based on plurality rule, the NP-Complete proof of vote control problem underk′-approval rule was also obtained.
查看全文   查看/发表评论  下载PDF阅读器
关闭