Class on Metric Graph Algorithms

 

Class number

202-2-6211

Schedule

Mon. 14:00-16:00, 97/206, Tue. 16:00-18:00, 97/205.

Office hours

Mine: Tue. 14:00-16:00 (Bldng 37, room 217),

Outline

Metric graph algorithms deal with computing distances in graphs, exactly and approximately. These algorithms often involve special metric combinatorial structures, such as spanning trees, metric trees, ultra-metrics, spanners, Steiner spanners, distance preservers, emulators, hopsets, and others. We will study these structures, their constructions, properties and applications. We will also discuss distance labeling schemes, metric-routing schemes, distance oracles, and low-distortion embeddings of graphs into metric (typically, Banach) spaces. The latter are closely related to metric combinatorial structures, and similar ideas are used for constructing both. Time-permitting, we will discuss most recent developments, such as terminal and prioritized metric structures, in which vertices with higher priorities enjoy better distortion and more compact representation than vertices with lower one.

General information

The grade of the course will be set as the weighted average of the grade of frontal exam (70%) and homework assignments (30%). There will be 4-8 homework assignments during the course. Students are allowed to skip one of those assignments. Assignments are for individual submission (submissions by groups of 2 and more students will not be accepted).

Syllabus

The design of metric graph algorithms is an active area of research. It has multiple applications in the areas of Graph Algorithms, Approximation Algorithms and Distributed Algorithms. The specific topics that will be covered (with possible variations due to time limitations, and the desires of the audience) are:

1) Relevant computational models, notions of spanners.

2) Basic algorithms for building (multiplicative) spanners, upper and lower bounds for both unweighted and weighted graphs. Relevant computational models.

3) Chernoff's bounds.

4) Cohen’s randomized algorithm for constructing maximum neighborhood covers.

5) Streaming model, and streaming algorithms for constructing multiplicative spanners.

6) Extension of the streaming algorithms to distributed model of computation.

7) Using these constructions for building edge covers.

8) Gallager-Humblet-Spira Baswana-Sen’s algorithm for building multiplicative spanners for weighted graphs.

9) Thorup-Zwick’s construction of distance oracles.

10) Thorup-Zwick’s routing.

11) Elkin-Pettie’s distance oracle.

12) Prioritized variants of distance oracles.

13) Additive and near-additive spanners.

The discussion will be conducted from mathematical perspective, trying to provide rigorous proofs wherever possible along with the intuition. The class will be self-contained, but will assume some basic knowledge of algorithmics and discrete mathematics.

Homework Assignments

Assignment 1
pdf format

Assignment 2
pdf format
Assignment 3
pdf format

Bibliography

The book of David Peleg, Distributed Computing: a Locality-Sensitive Approach, SIAM, Philadelphia, PA, 2000.
SIAM web-page of the book



My paper on constructing spanners in streaming and distibuted models
Streaming and Distributed Algorithm for Constructing Spanners


A paper of Thorup and Zwick about distributed routing
Compact Routing Schemes,

My paper with David Peleg on constructing near-additive spanners
(1+epsilon,beta)-spanners for general graphs

My paper with Seth Pettie on path-reporting distance oracles
A Linear-Size Logarithmic-Stretch Path-Reporting Distance Oracles for General Graphs

Thorup and Zwick's seminal paper on distance oracles
Approximate Distance Oracles

Assignments, Home Exam



Solutions to Assignments