THESIS
2017

xii, 209 pages : illustrations ; 30 cm

**Abstract**
Most graph algorithms run faster, sometimes by orders of magnitude, on sparse graphs (graphs
containing few edges). By approximating a dense input graph by a suitable sparse graph or other
data structure, one can improve an algorithm’s computation and storage efficiency. With this motivation,
this thesis concentrates on the problem of how to construct a compact data structure that
closely represents a given graph, as well as its related applications.

Our first focus is graph sparsification. The generic graph sparsification problem is to approximate
a given graph by a sparse graph (i.e., the graph sparsifier) on the same vertex set but retaining
only a smaller subset of edges. Such a sparsifier usually preserves, with bounded error, some quantitative
properties of the original g...[

Read more ]

Most graph algorithms run faster, sometimes by orders of magnitude, on sparse graphs (graphs
containing few edges). By approximating a dense input graph by a suitable sparse graph or other
data structure, one can improve an algorithm’s computation and storage efficiency. With this motivation,
this thesis concentrates on the problem of how to construct a compact data structure that
closely represents a given graph, as well as its related applications.

Our first focus is graph sparsification. The generic graph sparsification problem is to approximate
a given graph by a sparse graph (i.e., the graph sparsifier) on the same vertex set but retaining
only a smaller subset of edges. Such a sparsifier usually preserves, with bounded error, some quantitative
properties of the original graph, making it an appropriate candidate to replace the old graph
in some computations. We present faster randomized and deterministic algorithms for constructing
graph sparsifiers that preserve (up to small error) the value of every Laplacian quadratic form.

We then extend the idea of graph sparsification to creating a novel data structure—graph sketches.
Graph sketches differ from graph sparsifiers in two aspects: (i) Sketches can be any data
structure, not limited to graphs, and (ii) Sketches only preserve the value of every fixed Laplacian
quadratic form, with high probability. We present an algorithm for constructing nearly optimal
graph sketches, which uses much less storage than even the graph sparsifier, matching the lower
bound on the space size of sketches for storing graphs.

Finally, we investigate two problems closely related to graph theory: the design of solvers for
linear systems of equations, and the optimization of confluent network flows. For the former, we
develop a new algorithm for solving a linear system for a special class of PSD matrices, those which
can be decomposed into the sum of two almost commuting matrices. Our solver runs in time nearly
linearly depending on the input size, beating previous best solvers. For the latter, we prove the
logarithmic non-approximability of the single-sink Confluent Quickest Flow and Confluent Maximum
Flow Over Time problems, and present polylogarithmic approximation algorithms. To the
best of our knowledge, our algorithms are the first polynomial-time polylogarithmic approximation
algorithms for these problems in a general network.

## Post a Comment

Your email address will not be published. Required fields are marked *