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