权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

RUI: Embeddings of Discrete Metric Spaces into Banach Spaces

RUI：将离散度量空间嵌入 Banach 空间

基本信息

批准号：
1953773
负责人：
Mikhail Ostrovskii
金额：
$ 19.46万
依托单位：
Saint John's University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-07-01 至 2024-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1953773&HistoricalAwards=false
关键词：
RUI Embeddings Discrete Metric Spaces

项目摘要

Analysis of large sets of data is important in many contexts. Usually data is endowed with a natural distance or metric (degree of dissimilarity) of its elements. One of the useful approaches to analysis of such sets of data is to use some low-distortion embeddings of the set into a space whose structure is well-known; for example, into a two-dimensional or three-dimensional space. The more general spaces considered are called Banach spaces. After that one can use many algorithms available in computational geometry and many tools from classical parts of mathematics such as Calculus. If a low-distortion embedding into a plane is available, one can even visualize the structure of the set; for example, it is possible to see its clusters. Another application of embeddings is to construction of approximate algorithms. This means that in cases where the algorithms for finding the exact solution of a combinatorial optimization problem are not practical (i.e., consume too much time) we are looking not for the optimal solution, but for a solution close (in one or another sense) to being optimal. In many cases, the best known approximate algorithms for exact solutions are based on metric embeddings. The main goal of this project is to study embeddings of discrete metric spaces into Banach spaces. Such embeddings form a well-established tool in Theoretical Computer Science and Topology. The existence of a low-distortion embedding into a plane is rather rare in applications. In many contexts, weaker types of embeddings are still useful, and even embeddings into high-dimensional or infinite-dimensional Banach spaces lead to important results. The PI will study embeddings of discrete metric spaces into Banach spaces. This project will contribute to the following general problem: Find new classes of embeddings of finite and locally finite metric spaces into Banach spaces and find new types of obstructions to such embeddings. The main directions of proposed work are: 1. Study relations between embeddability into different classes of Banach spaces, expansion, and girth of graphs. 2. Study geometric properties of transportation cost spaces, known to contain isometrically metric spaces on which they are built. 3. Find characterizations of well-known classes of Banach spaces in terms of embeddings. 4. Study relations between embeddability of metric spaces and embeddability of their parts. The methods are expected to be a mixture of methods of geometric functional analysis and graph theory, with occasional usage of methods of probability theory and geometric group theory.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

在许多情况下，大型数据集的分析都很重要。通常，数据被赋予其元素的自然距离或度量(相异度)。分析这样的数据集的有用方法之一是使用集合的一些低失真嵌入到其结构是众所周知的空间中；例如，嵌入到二维或三维空间中。所考虑的更一般的空间称为Banach空间。在此之后，人们可以使用计算几何中的许多算法和微积分等数学经典部分中的许多工具。如果可以将低失真嵌入到平面中，人们甚至可以可视化集合的结构；例如，可以看到它的簇。嵌入的另一个应用是构造近似算法。这意味着，在寻找组合优化问题的精确解的算法不实用(即，耗费太多时间)的情况下，我们寻找的不是最优解，而是(在某种意义上)接近最优解的解。在许多情况下，最著名的精确解的近似算法是基于度量嵌入的。这个项目的主要目的是研究离散度量空间到Banach空间的嵌入。这样的嵌入形成了理论计算机科学和拓扑学中一个成熟的工具。低失真嵌入到平面中的存在在应用中相当少见。在许多情况下，较弱类型的嵌入仍然有用，甚至嵌入到高维或无限维Banach空间中也会产生重要的结果。PI将研究离散度量空间到Banach空间的嵌入。这个项目将致力于以下一般性问题：找到有限和局部有限度量空间到Banach空间的新的嵌入类型，并找到这种嵌入的新类型的障碍。本文的主要工作是：1.研究不同Banach空间类的可嵌入性与图的扩展、围长之间的关系。2.研究运输成本空间的几何性质，已知运输成本空间包含等距度量空间，它们建立在等距空间上。3.找出熟知的Banach空间类的嵌入刻画。4.研究度量空间的可嵌入性与其各部分的可嵌入性之间的关系。这些方法预计将是几何泛函分析和图论方法的混合，偶尔会使用概率论和几何群论的方法。这个奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。