Collaborative Research: Greedy Approximations with Nonsubmodular Potential Functions

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

• 批准号: 0728851
• 负责人: Ding-Zhu Du
• 金额: $ 25.01万
• 依托单位: University of Texas at Dallas
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-15 至 2012-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0728851&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 开发了新技术来分析其中一些。他们建议将他们的技术扩展到其他贪婪启发法，以解决计算机系统、计算机网络和计算分子生物学引起的问题。因此，该研究将产生以下更广泛的影响：它将增强近似算法的设计和分析以及优化理论的先进理论，并将为一些计算机系统和工程领域（包括计算机网络和计算分子生物学）的发展提供帮助。 。 所提出的近似/启发式将为这些领域产生的优化问题提供出色的解决方案。研究生的参与将给未来带来许多好处。学生的发现和研究经验将为他们在影响科学和工程基础发展的非常重要的当前研究领域的学术界、研究实验室和工业界的富有成效的职业生涯做好准备。