Class on Metric Graph Algorithms
Mon. 14:00-16:00, 97/206, Tue. 16:00-18:00, 97/205.
Mine: Tue. 14:00-16:00 (Bldng
37, room 217),
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.
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).
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:
The book of David Peleg, Distributed Computing: a
Locality-Sensitive Approach, SIAM, Philadelphia, PA, 2000.