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

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

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.