AF: Small: Future Directions in Approximation Algorithms Research

AF：小：近似算法研究的未来方向

基本信息

批准号：
1016799
负责人：
Anupam Gupta
金额：
$ 39.42万
依托单位：
Carnegie-Mellon University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2010
资助国家：
美国
起止时间：
2010-09-01 至 2015-08-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1016799&HistoricalAwards=false
关键词：
AF Small Future Directions Approximation

项目摘要

This research is focused on general area of approximation and online algorithms. Many commonly studied optimization problems are intractable, and it is natural to approximate the optimum instead. While there has been much progress on such problems in the past two decades, there is much work to be done. This research investigates some long-standing open problems of interest, it also extends the techniques beyond what is currently known, and the research also investigates richer models and problems that attempt to capture the complexity and diversity of optimization problems that arise in practice. Along the problems considered in this research is that of formulating and solving optimization problems in the presence of partial information, which is often a requirement in practice. Another class of problems concerns the algorithmic theory of finite metric spaces, and this research further investigates the embeddability of graph metrics into normed spaces.This research broadens the scope of understanding of approximation algorithms for optimization problems by developing models and problem formulations inspired by the aspects of practicality, and by developing algorithms and algorithmic techniques which will be relevant in broader contexts. Research progress is propagated into the curriculum via specialized courses presenting the theoretical advances in the context of their applications, as well as basic courses teaching the fundamental ideas and techniques behind these research advances.

这项研究的重点是近似和在线算法的一般领域。许多通常研究的优化问题都是棘手的，因此很自然地会逼近最优值。尽管过去二十年来在这些问题上取得了很大进展，但仍有许多工作要做。这项研究调查了一些长期存在的感兴趣的开放问题，还将技术扩展到目前已知的范围之外，并且研究还调查了更丰富的模型和问题，试图捕捉实践中出现的优化问题的复杂性和多样性。本研究考虑的问题是在存在部分信息的情况下制定和解决优化问题，这通常是实践中的要求。另一类问题涉及有限度量空间的算法理论，本研究进一步研究了图度量在赋范空间中的嵌入性。本研究通过开发受以下方面启发的模型和问题表述，拓宽了对优化问题的近似算法的理解范围实用性，并开发在更广泛的背景下相关的算法和算法技术。研究进展通过专业课程和基础课程传播到课程中，专业课程介绍其应用背景下的理论进展，基础课程教授这些研究进展背后的基本思想和技术。