Collaborative Research: Greedy Approximations with Nonsubmodular Potential Functions

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

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.