Techniques in Approximation Algorithms

近似算法技术

• 批准号: 0430650
• 负责人: Samir Khuller
• 金额: --
• 依托单位: University of Maryland, College Park
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-09-01 至 2009-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0430650&HistoricalAwards=false
• 关键词: Techniques; Approximation; Algorithms

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.

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