AF: Small: Future Directions in Approximation Algorithms Research

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

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.