Techniques in Approximation Algorithms

本项目旨在研究NP-Hard优化问题的可逼近度度量和启发式设计。这一努力将导致技术的发展，使人们能够更深入地理解设计NP-Hard问题近似算法的基本原理。近似算法是一种多项式时间算法，它能产生可证明接近最优解。我们研究的许多问题都是图论问题。图是一种强大的工具，可以用来建模对象以及它们之间的关系。事实上，许多不同的优化问题都可以用图论的术语来描述。具体地说，图论提供了一种很好的方法来对与运输、网络设计/路线、设施选址和聚类分析等领域相关的问题进行建模。这个强大的框架允许我们开发和演示不同算法工具的强大功能。除了图形问题，我们还研究了一些基本的调度、数据管理和广播问题。智力上的优点：增加对开发和应用近似算法的技术的理解将对研究和实践产生重大影响。众所周知，NP完备性问题在许多科学和工程学科中大量存在，任何有效应对这一困难的技术都将对启发式的设计产生重大影响。更广泛的影响：更广泛的科学目标是根据我们对哪些问题可以有效解决，哪些问题不能有效解决的理解，来推动算法领域的发展。此外，我们还探索了这些算法在其他领域的应用，如网络、网格计算、并行计算等。该项目将培训两名全日制博士生在大学进行研究，并在暑期通过在国家实验室和工业研究中心的实习进行研究。

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 understandingof 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 tomodel objects, as well as the relationships between them. Indeed, many distinct optimization problems can becast in graph theoretic terms. Specifically, graph theory provides an excellent way to model problems relatedto areas such as transportation, network design/routing, facility location, and cluster analysis. This powerfulframework allows us to both develop and illustrate the power of different algorithmic tools. In addition tograph 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 completeproblems are abundant in many scientific and engineering disciplines, any technique that effectively copeswith 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 ourunderstanding of what problems can be solved efficiently and what problems cannot. In addition, we exploreapplications 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 throughinternships during the summer at National Labs and Industrial Research Centers.