CCF-BSF: AF: Small: Metric Embeddings and Partitioning for Minor-Closed Graph Families

CCF-BSF：AF：小：次封闭图族的度量嵌入和分区

• 批准号: 1617790
• 负责人: Anupam Gupta
• 金额: $ 45万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-07-01 至 2019-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1617790&HistoricalAwards=false
• 关键词: CCF; BSF; AF; Small; Metric

The interaction between algorithm design and metric embeddings has been a very fruitful one. Over the past two decades, the toolbox of metric embeddings has become an indispensable one for the algorithm designer. The reason is simple: embeddings give a set of techniques to simplify graphs and metric spaces. This has led to approximation algorithms for many graph partitioning and network design problems. In turn, better graph decompositions have led to better embeddings. Nevertheless, the interplay between graph topology and the metric geometry is not fully understood. This proposal focuses on developing new techniques for interesting families of graphs. Broader impacts include the engagement of undergraduate students and women in research, and the training of graduate students and postdoctoral associates. Moreover, the proposed research should help develop deeper connections between computer science and mathematics. Being part of a joint initiative between NSF and the US-Israel Binational Science Foundation, this project will increase collaboration between researchers working on similar topics in the United States and Israel.The technical aspects of the research focus on questions in metric embeddings and graph partitioning for planar, bounded tree-width and path-width graphs, and general minor-closed families of graphs. These include getting better low-diameter partitions for these families via the bounded-threatener program, getting better L1 and tree embeddings, and improved metric and graph compression techniques, such as improved vertex-sparsifiers and spanners.

算法设计和度量嵌入之间的相互作用是非常富有成效的。在过去的二十年里，度量嵌入工具箱已经成为算法设计者不可或缺的工具箱。原因很简单：嵌入提供了一组简化图和度量空间的技术。这导致了许多图划分和网络设计问题的近似算法。反过来，更好的图分解带来了更好的嵌入。 然而，图拓扑和度量几何之间的相互作用尚未完全理解。该提案的重点是为有趣的图族开发新技术。 更广泛的影响包括本科生和女性参与研究，以及研究生和博士后的培训。此外，拟议的研究应有助于在计算机科学和数学之间建立更深入的联系。作为 NSF 和美国-以色列两国科学基金会联合计划的一部分，该项目将加强美国和以色列研究类似主题的研究人员之间的合作。该研究的技术方面重点关注度量嵌入和图划分中的问题用于平面、有界树宽度和路径宽度图，以及一般的小闭族图。 其中包括通过有界威胁程序为这些族获得更好的低直径分区，获得更好的 L1 和树嵌入，以及改进的度量和图压缩技术，例如改进的顶点稀疏器和扳手。