Collaborative Research: Greedy Approximations with Nonsubmodular Potential Functions

合作研究：非次模势函数的贪婪逼近文献中提出了许多贪婪优化算法。然而，并不是很多都能成功地分析出来。实际上，现有的贪婪逼近分析方法大多需要势函数的次模性。对于具有非次模势函数的贪婪算法，分析是一个很大程度上未探索的开放领域。事实上，许多在计算实验中有很好的表现，但没有得到太多的理论分析，由于难以处理nonsubmodular潜在的功能。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.