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.

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