Collaborative Research: MSPA-MCS: Embeddings of Finite Metric Spaces - A Geometric Approach to Efficient Algorithms

合作研究：MSPA-MCS：有限度量空间的嵌入 - 高效算法的几何方法

• 批准号: 0528414
• 负责人: Sanjeev Arora
• 金额: $ 29万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-09-15 至 2010-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0528414&HistoricalAwards=false
• 关键词: Collaborative; Research; MSPA; MCS; Embeddings

Geometry has become a central notion in algorithm design, in fieldsas diverse as bioinformatics and graph partitioning.This research is a concerted and unified attack on a large subset of theunderlying mathematical problems, which often have to do withgeometric embeddings of finite metric spaces.The concrete applications range from clustering and learning tocompact representation of data to graph partitioning tonearest neighbor searching. Since the research spans aa variety of fields, the assembled team is multidisciplinary,involving analysts (Johnson and Naor), a geometer (Gromov),a discrete mathematician and combinatorialist (Linial)and algorithm designers (Arora and Charikar).The research area emerging from the ongoing geometrization ofalgorithms is an exciting new frontier for both mathematics andcomputer science. For example, deep mathematical results such asLipschitz extension may turn out to have applicationsto the practical problem of compactly representing computer sounds.In turn, algorithmic settings provide a fertile new ground formathematical theory. The investigators study geometric representationsfor data and low disortion mappings into structured spaces. Metrics thatarise in the design of approximation algorithms for NP-hard problems arestudied, especially to understand their local versus global properties.The research develops new understanding for practicallyimportant metrics such as earth mover and edit distancemetrics, which are defined in terms of computational effort and havethus not been studied in mathematics.