基于d-approval规则的社会学难解问题参数算法研究

来源 :中南大学 | 被引量 : 0次 | 上传用户:guoerxong
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
社会学中投票问题的研究由来已久,现在它已经广泛地应用于计算理论领域,在人工智能、生物信息学以及图编辑问题中扮演了重要角色。参数计算理论是精确求解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问题的参数复杂性。通过对这两个问题的剖析,简化了问题实例的规模,设计了固定参数算法,拓展了参数计算的应用范畴,丰富了投票问题的研究思路。
其他文献
随着物联网技术的出现及不断发展,作为物联网感知层关键技术之一的无线传感器网络技术也受到越来越多的关注。无线传感器网络在灵活性、容错性、低功耗及快速部署方面具有特
微博拥有信息多元、表达快捷、互动性强等传统媒体无法比拟的优势,迅速发展为人际交互及信息传播的主要方式,在商品营销、舆情传播等方面有着广泛的应用。影响力的问题被引入到
摘要:经典智能规划问题是人工智能研究领域里最为重要的问题之一。但是由于其时间复杂度上的不可跟踪性,使得这项技术在实际应用中的范围十分受限,所以一直以来,与智能规划有
工作流成批处理,是指将同一类型活动的多个工作流活动实例进行整合处理,使得原本多个工作流活动实例的分别执行变成组合执行,从而降低活动执行成本和提高活动执行效率。然而,由于
随着我国城市化进程的加快,城市机动车数量在急剧增长,这对传统的交通管理方法提出了新的挑战。目前,交通管理问题已成为城市管理的重要问题。现代智能交通管理系统就是为应对城
随着人机交互,三维动画,游戏,体育运动分析,医疗诊断和虚拟现实等领域的迅速发展,人体运动捕获系统作为其关键技术,已成为这些领域的研究重点。目前市场上,基于带标记点的人体运动捕
随着web2.0时代的到来,网络已经成为人们生活与交流的重要工具。人们在网络上发表对某一事件或者产品的意见或者评论。如何挖掘产品评论中的有用信息即意见挖掘任务,成为自然语
本论文隶属于国家自然科学基金项目:无线传感器网络中基于时间序列相关性的低能耗数据获取方法研究(No.60970112)。无线传感器网络应用规模日趋扩大,因其能源限制等特点导致故障
遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种全局概率搜索算法。鉴于该算法具有收敛速度太慢、容易陷入局部最优解的缺点,本文结合模拟退火机制、小生境技术
汽车产业的不断发展在给我们带来便利的同时,也产生了很多其它问题,如:城市交通拥堵、道路交通事故以及恶劣天气下道路交通安全等。车载自组织网络(VehicularAd hoc Networks, VA