Collaborative Research: Greedy Approximation with Nonsubmodular Potential Functions
Presented 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.
