Monday, July 26, 2021 - 10:00am to 11:00am
Location:Virtual Presentation - ET Remote Access - Zoom
Speaker:DAVID (ELLIS) HERSHKOWITZ, Ph.D. Student https://dhershko.github.io/
Compact Representations of Graphs and Their Metrics
Graphs and metrics are two of the most ubiquitous, versatile and powerful tools in modern computing. Both are general enough to be widely applicable but structured enough to facilitate efficient algorithms. However, the modern proliferation of data has led to graphs and metrics of practical importance which are of unprecedented size. For this reason, now more than ever, understanding how to sparsify or otherwise effectively reduce the size of a graph or metric is of great importance. We propose new results in graph and metric sparsification using tools from combinatorial optimization, metric embeddings, approximation algorithms and online algorithms.
In the first part of this thesis proposal we provide new results on and directions for classical questions in graph and metric sparsification. First, we propose a new sort of tree embedding of metrics which embeds each point in a metric into boundedly-many copies. Using these embeddings we give the first non-trivial deterministic algorithm for online group Steiner tree and the demand robust version of many Steiner problems. Second, we give a new attack and preliminary results on one of the most basic sparsification questions in directed graphs: how to find a minimum cardinality subgraph which preserves all connectivity relationships between vertices.
In the second part of this proposal we investigate how the interactions between a graph and its induced metric affect compact representations. First, we study how to overcome the challenges of meaningfully incorporating graph structure in the form of hop-constraints into metric embeddings and network design problems. In particular, we give the first tree embeddings for the hop-constrained distances in a graph. Using these embeddings we give the first poly-log bicriteria algorithms for the hop-constrained version of many classic network design problems. Second, we investigate how graph structure can make metric sparsification easier. In particular, we study the Steiner point removal problem where we must vertex-sparsify a graph from a structured family. We give the first O(1) distortion Steiner point removal solutions on series-parallel graphs as well as new approaches for Steiner point removal in planar graphs.
Bernhard Haeupler (Co-Chair)
R. Ravi (Co-Chair)
Michel Goemans (Massachusetts Institute of Technology)
Ola Svensson (École polytechnique fédérale de Lausanne ‐ EPFL)
Zoom Participation. See announcement.