简单规则下Vote Control问题的复杂性分析
DOI:
作者:
作者单位:

作者简介:

通讯作者:

基金项目:

河南省科技攻关项目(122102310442)


The complexity of Vote Control problem under simple rules
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
    摘要:

    给定候选人集合C,投票集合V=(v1,v2,…,vn)和候选人c∈C,是否存在V的子集V′,|V′|≤k,使得c∈r(V\V′).该问题在不同的得分规则下复杂性是不同的.在plurality规则的基础上证明了Reto规则下Vote Control问题是多项式时间可解的,并给出了k′-approval规则下该问题是NP-Complete的证明.

    Abstract:

    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.

    参考文献
    相似文献
    引证文献
引用本文

秦勤,王雪瑞,李建.简单规则下Vote Control问题的复杂性分析[J].湖南科技大学学报(自然科学版),2013,28(1):84-86

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
历史
  • 收稿日期:
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期: 2013-06-09