This project aims to study the approximability measures and the design of heuristics for NP-hard optimiza- tion problems. This endeavor will result in the development of techniques that enable a deeper understanding of the principles that underlie the design of approximation algorithms for NP-hard problems. An approxima- tion algorithm is a polynomial time algorithm that produces solutions provably close" to optimal. Many of the problems we study are graph theoretic. Graphs are powerful tools that can be employed to model objects, as well as the relationships between them. Indeed, many distinct optimization problems can be cast in graph theoretic terms. Specifically, graph theory provides an excellent way to model problems related to areas such as transportation, network design/routing, facility location, and cluster analysis. This powerful framework allows us to both develop and illustrate the power of different algorithmic tools. In addition to graph problems, we also study some fundamental scheduling, data management and broadcasting problems. Intellectual Merit: An increased understanding of techniques to develop and apply approximation algo- rithms will have a significant impact on both research and practice. As we are well aware, NP complete problems are abundant in many scientific and engineering disciplines, any technique that effectively copes with this diffculty will have a significant impact on the design of heuristics. Broader Impact: The broader scientific goals are to both further the field of algorithms in terms of our understanding of what problems can be solved efficiently and what problems cannot. In addition, we explore applications of these algorithms in other areas such as networking, GRID computing, parallel computing etc. The project will train two full time PhD students in conducting research both in Universities and through internships during the summer at National Labs and Industrial Research Centers.
