A Spectral Approach to Network Design

Explore a spectral approach to network design in this 24-minute conference talk presented at the Association for Computing Machinery (ACM). Delve into topics such as iterative rounding, spectral and electrical network design, and generalized survivable network design. Learn about Laplacian matrices and graph cuts, and discover the first and second main results of the research. Examine the one-sided spectral rounding algorithm, its analysis, and implications. Gain insights into cutting-edge techniques for solving complex network design problems and their potential applications in computer science and engineering.

Syllabus

Intro
Outline
Iterative Rounding
More Constraints?
Spectral Network Design
Electrical Network Design
Generalized Survivable Network Design
First Main Result
Example
Second Result
Laplacian Matrix and Graph Cuts . Given x ER , define Laplacian matrix of the fractional solution
Spectral Rounding for Network Design
Our Result for One-Sided Spectral Rounding
Algorithm
Analysis
Remarks
Conclusion