排序问题的博弈分析和多目标排序

项目名称： 排序问题的博弈分析和多目标排序

项目编号： No.10971191

项目类型： 面上项目

立项/批准年度： 2010

项目学科： 数理科学和化学

项目作者： 谈之奕

作者单位： 浙江大学

项目金额： 24万元

中文摘要： 排序理论是运筹学组合最优化领域中研究最为活跃的分支之一，本项目将深入研究排序的两个新课题：排序问题的博弈分析和多目标排序问题，核心内容是算法设计和最坏情况分析。对排序博弈，研究均衡排序的存在性及其性质，设计符合要求的排序机制。对多目标排序问题，考虑算法的双目标最坏情况界，以及多组竞争工件、工件或机器可选择等模型。我们还将研究应用领域的一些具体排序问题。对以上这些问题，我们将探讨它们的计算复杂性、多项式时间近似方案的存在性或难近似性，以及快速近似算法的设计。这些问题国际上的研究刚刚起步或起步不久，有较大难度，本项目将对它们进行前瞻性研究，获得创新性成果。

中文关键词： 排序；算法设计与分析；最坏情况界；Nash均衡；

英文摘要：

英文关键词： Scheduling；Analysis of algorithms；Worst-case analysis；Nash Equilibrium；