PhD Seminar • Algorithms and Complexity — A Spectral Approach to Network Design

Wednesday, June 17, 2020 2:15 pm - 2:15 pm EDT (GMT -04:00)

Please note: This PhD seminar will be given online.

Hong Zhou, PhD candidate
David R. Cheriton School of Computer Science

In this talk, I will present a spectral approach to design approximation algorithms for network design problems. We observe that the underlying mathematical questions are the spectral rounding problems, which were studied in spectral sparsification and in discrepancy theory. We extend these results to incorporate additional non-negative linear constraints, and show that they can be used to significantly extend the scope of network design problems that can be solved. Our algorithm for spectral rounding is an iterative randomized rounding algorithm based on the regret minimization framework. In some settings, this provides an alternative spectral algorithm to achieve constant factor approximation for the classical survivable network design problem.

This work is joint with Lap Chi Lau. The full manuscript is available on arXiv at: https://arxiv.org/abs/2003.07810

To join this PhD seminar virtually, please go to https://zoom.us/j/96953389338

Meeting ID: 969 5338 9338