Collaborative Research: Greedy Approximations with Nonsubmodular Potential Functions

协作研究：具有非子模势函数的贪婪近似

• 批准号: 0728812
• 负责人: Haesun Park
• 金额: $ 17.88万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-15 至 2011-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0728812&HistoricalAwards=false
• 关键词: Collaborative; Research; Greedy; Approximations; Nonsubmodular

Collaborative Research: Greedy Approximation with Nonsubmodular Potential FunctionsPresented in the literature are many greedy optimization algorithms. However, not many of them can be successfully analyzed. Actually, most existing techniques for analysis of greedy approximation require the submodularity of potential functions. For greedy heuristics with nonsubmodular potential functions, the analysis is a largely unexplored open area. Indeed, many have good performance in computational experiments, but have not received much theoretical analysis due to the difficulty of dealing with nonsubmodular potential functions. The PIs have developed new techniques to analyze some of them. They propose to extend their techniques to other greedy heuristics for problems arising from computer system, computer networks and computational molecular biology. Therefore, the research will have the following broader impacts: It will enhance advanced theory for design and analysis of approximation algorithms and the theory of optimization and will provide helps in development of in some computer systems and engineering areas, including computer networking and computational molecular biology. The proposed approximations/heuristics will provide excellent solutions for optimization problems arising from those areas. The graduate student involvement will have numerous future benefits. The discovery and research experience of the students will prepare them for productive careers in academia, research labs, and industry in highly important, current research areas affecting fundamental development in science and engineering.

非子模势函数的贪心逼近在文献中提出了许多贪心优化算法。然而，能够被成功分析的并不多。实际上，现有的贪心逼近分析方法大都要求利用势函数的子模性。对于具有非次模势函数的贪心启发式算法，其分析在很大程度上是一个未开发的开放区域。事实上，许多方法在计算实验中表现良好，但由于处理非次模势函数的困难，没有得到太多的理论分析。pi已经开发了新的技术来分析其中的一些。他们建议将他们的技术扩展到计算机系统、计算机网络和计算分子生物学中出现的其他贪婪启发式问题。因此，该研究将产生以下更广泛的影响：它将提高设计和分析近似算法和优化理论的先进理论，并将为一些计算机系统和工程领域的发展提供帮助，包括计算机网络和计算分子生物学。提出的近似/启发式方法将为这些领域产生的优化问题提供出色的解决方案。研究生的参与将有许多未来的好处。学生的发现和研究经验将为他们在学术界、研究实验室和工业中从事影响科学和工程基础发展的非常重要的、当前的研究领域的富有成效的职业做好准备。