CAREER: Algorithmic Theory and Applications of Metric Emeddings

这份职业发展计划专注于度量嵌入，这是算法研究的一个强大领域。对嵌入的兴趣源于它们广泛的算法适用性；它们被广泛用于获得简单、优雅和通用的解决方案和设计算法。度量嵌入的使用通常允许特殊方法被强大的通用原则取代，并提出了解决长期悬而未决的问题的新方法。这些技术的影响可以在寻找图形分隔符、数据集群、网络设计、流计算以及几何和在线算法等问题上看到，仅举几例。本研究的目的是在这些应用的背景下集中研究嵌入的算法理论。非正式地说，嵌入是将任意度量空间映射到不会改变太多距离的“较简单”度量空间的映射，本研究的重点是两个自然和基本的主题：(A)从算法的角度研究度量空间的复杂性，并利用这一点来开发有效的算法；(B)开发简化度量的嵌入；即将一般度量空间嵌入到众所周知的较简单度量空间中。这一建议为研究生和本科生提供了广泛的研究机会：包括理论原理的调查，算法和嵌入的开发，以及对这些结果的实施和实验评估。这项研究的进展将通过特殊课程影响课程，展示理论进步及其应用。将利用讲习班和研讨会促进跨学科研究。

This Career Development Plan is focused on Metric Embeddings, a powerful area of algorithms research. Interest in embeddings stems from their broad algorithmic applicability; they are being used extensively toobtain solutions and design algorithms that are simple, elegant and versatile. The use of metric embeddings has often allowed ad-hoc methods to be replaced by powerful general principles, and has suggested newapproaches to tackle long-standing open problems. The impact of these techniques can be seen on problems in finding graph separators, data clustering, network design, streaming computation, and geometric andon-line algorithms, to name but a few. This research intends to focus on the algorithmic theory of embeddings in the context of these applications. Informally, an embedding is a map of an arbitrary metric space into a ``simpler'' one which does not alter distances by much, and the focus of this research is on two natural and fundamental themes: (a) to investigate the complexity of metric spaces from an algorithmic perspective, and to use this to develop efficient algorithms, and (b) to develop embeddings that simplify metrics; i.e. embed general metric spaces to well-understood simpler ones.This proposal offers a broad spectrum of research opportunities at both graduate and undergraduate levels: these include the investigation of theoretical principles, the development of algorithms and embeddings, and the implementation and experimental evaluation of these results. Progress in this research will influence the curriculum via special courses presenting theoretical advances along with their applications. Workshops and seminars will be used to promote interdisciplinary research.