项目简介
项目名称
基于非次模势函数的贪婪近似算法的设计与分析
项目批准号
11071191
学科分类
A011202
数理科学部
_数学
_运筹学
_组合最优化
资助类型
数理科学
负责人
王卫
依托单位
西安交通大学
批准年份
2010
起止时间
201101-201312
批准金额
27.00万元
摘要
在科学理论及工程实践中存在大量的贪婪算法。然而，并非所有贪婪算法的好坏都能够在理论上得到成功的分析。现有的大多数分析贪婪近似算法的技巧都依赖于次模势函数,而如何设计与分析带非次模势函数的贪婪近似算法，则在很大程度上仍是一片亟待开垦的未知领域。本项目拟以概率分析等多种方法为工具，研究由不同应用领域（如无线传感器网络，社会网络等）提出的一些具有重要应用价值的NP-难组合优化问题，尤其是研究那些带非次模势函数的组合优化问题的贪婪近似算法。我们的研究目标是，通过对这些具体问题的研究，发展出基于非次模势函数的贪婪近似算法的新的理论和方法，从而进一步将其应用到更为一般的组合优化问题中。该项目的顺利完成将为组合优化及理论计算机领域的研究带来新的重要进展，同时也为应用领域的工作者如何设计更好的经验算法带来有益的启示。
评论区 (0)
#插入话题
