Computer Science Thesis Oral
— 1:00pm
Location:
Virtual Presentation - ET
-
Remote Access - Zoom
Speaker:
DAVID HERSHKOWITZ
,
Ph.D. CandidateComputer Science DepartmentCarnegie Mellon University
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. Furthermore, 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 give 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 we provide two new so-called tree embeddings which represent relevant aspects of an arbitrary input graph by a tree. Using these embeddings we give the first non-trivial deterministic approximation algorithms for online group Steiner tree and the online covering Steiner tree problem as well as the first poly-log bicriteria algorithms for the hop-constrained version of many classic network design problems.
In the second part of this thesis we provide new algorithms for a primitive at the heart of recent advances in expander decompositions for graphs. Specifically, we give the first algorithms for (1 − ϵ)-approximate h-length flows running in sequential time tilde{O}(m poly(h, 1/eps)) , parallel time tilde{O}(poly(h, 1/eps)) with m processors and distributed CONGEST time tilde{O}˜(2^{O(root(log n))} ·poly(h, 1/eps)). We give a variety of applications including simplified distributed and deterministic constructions of expander decompositions, efficient algorithms for computing h-length cutmatches which form the backbone of recent work in hop-constrained expander decompositions and what is to our knowledge the first non-trivial distributed (1 - eps)-approximation for b-matching.
In the last part of this thesis 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 metric decompositions for series-parallel graphs.
Thesis Committee: Bernhard Haeupler (Co-Chair) R. Ravi (Co-Chair) Anupam Gupta Michel Goemans (Massachusetts Institute of Technology) Ola Svensson (EPFL) Zoom Participation. See announcement.
For More Information:
deb@cs.cmu.edu