This project focuses on designing and analyzing fast approximation algorithms for NP-hard problems, with good performance guarantees. Despite the recent strong results on the hardness of approximations, the PI and his Ph.D. Student have been instrumental in introducing new methodologies for designing and analyzing approximation algorithms, and in improving the best known performance guarantees for a wide range of problems. In particular, the goals of this project include: (1) Development and refinement of methodologies to design and analyze approximation algorithms; (2) The deviation of approximation algorithms with improved performance guarantees for a variety of combinatorial problems;(3)The actual solution of important practical problems, arising in electrical engineering and computer science, in computational molecular biology, and in material science. The Integrated Educational Plan of this CAREER Grant includes: (1) Involvement of undergraduates in developing efficient software codes based on approximation algorithms; (2) Development of undergraduate and graduate course which address the changing job markets; (3) Development of a multimedia textbook on optimization algorithms.***
