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

声明

摘要

1 绪论

1．1 课题研究背景

1．2 课题研究内容

1．3 课题研究意义

1．4 论文组织

2 社会学概述

2．1 确定赢家类问题

2．1．1 Kemeny投票系统

2．1．2 Dodgson和Young投票系统

2．2 确定可能的赢家

2．3 Control，Manipulation和Bribery

2．3．1 Copelanda规则下Candidate Control问题的复杂性

2．3．2 d-approval规则下Candidate Control问题的复杂性

2．4 本章小结

3 cc-dv-d-approval问题及其对偶问题的参数复杂性

3．1 引言

3．2 问题的定义及研究现状

3．3 参数复杂性研究

3．3．1 NP完全证明

3．3．2 问题的核

3．3．3 基于动态规划的固定参数算法

3．4 对偶问题的参数复杂性

3．4．1 对偶问题的NP完全证明

3．4．2 问题的结构分析

3．4．3 基于局部贪婪的固定参数算法

3．5 本章小结

4 cc-av-d-approval问题的参数算法研究

4．1 问题的定义及研究现状

4．2 NP完全证明

4．3 问题的结构分析

4．4 固定参数算法研究

4．5 本章小结

5 Bribery问题的参数复杂性

5．1 问题的定义及研究现状

5．2 NP完全证明

5．3 Bribery by voters问题的参数复杂性

5．4 本章小结

6 总结和展望

6．1 总结

6．2 工作展望

参考文献

攻读硕士期间主要研究成果

致谢