论文部分内容阅读
社会学中投票问题的研究由来已久,现在它已经广泛地应用于计算理论领域,在人工智能、生物信息学以及图编辑问题中扮演了重要角色。参数计算理论是精确求解NP难问题的新方法,受到人们的普遍关注。本文主要研究参数计算理论在社会学投票问题中的应用,讨论d-approval规则下Control和Bribery对投票问题的影响。主要研究工作和创新点如下: 本文研究了cc-dv-d-approval问题及其对偶问题,探讨删除投票对选举的影响。通过构造二分图,剖析了问题的结构和性质,给出了能降低规模的核心化规则。在cc-dv-d-approval问题中,去掉了与给定的候选人c相关的投票以及得分低于S(c)的候选人,得到了O(kd+3)的核。在此基础上提出了基于动态规划的时间复杂度为O*(2k2)的固定参数算法。在对偶问题中,通过分析发现该问题与经典的Set Packing问题存在一定的联系。当d=3时,本文提出了基于局部贪婪的时间复杂度为O*((3k)4k)的固定参数算法。 cc-av-d-approval问题以增加的投票个数作为参数,通过分析,新增加的投票必须支持给定的候选人c。为了使得c成为赢家,其它候选人增加的得分必须小于常数b。该问题可以看作是Set Packing问题的扩展。当d=4时,本文提出了基于局部贪婪的时间复杂度为O*((3k)4k)的固定参数算法。 Bribery主要通过贿赂投票使得给定的候选人成为赢家。本文研究Bribery by voters问题和Bribery by exchange问题,分别以贿赂的投票个数、投票的更改次数作为参数。在Bribery by voters问题中,通过分析问题的结构,得出结论,解集中的投票一定不支持候选人c。给出了核心化规则,得到了O(kd+3)的多项式核,从而证明了该问题在d>2时是固定参数可解的。最后证明了Bribery by exchange问题是多项式时间可解的。 综上所述,本文主要研究Control问题和Bribery问题的参数复杂性。通过对这两个问题的剖析,简化了问题实例的规模,设计了固定参数算法,拓展了参数计算的应用范畴,丰富了投票问题的研究思路。