Wednesday, March 25, 2020
Zoom Meeting ID: 779 730 106
University of Victoria
Structures in algorithm design: power and limits
Real-world graphs abound with structures: peer-to-peer networks have bounded growth; road networks are planar; social networks have small separators. How do we take these structures to algorithmic advantage?
In this talk, I will describe three types of structures to model different aspects of real-world graphs: bounded geometry, bounded clique minor, and small separation. I will discuss techniques to leverage these structures in algorithm design and the limits on the advantage we can gain by adopting them. Concretely, I will focus on three different algorithmic problems: constructing spanners, approximating the Traveling Salesperson Problem, and analyzing local search heuristics. Finally, I will discuss some directions for future research.
Hung Le is currently a Pacific Institute for the Mathematical Sciences (PIMS) postdoc at the University of Victoria with Valerie King. He received a Ph.D. in Computer Science from Oregon State University (2013-2018) advised by Glencora Borradaile and a B.S. degree in Computer Science from Hanoi University of Science and Technology (2007-2012). He is interested in algorithms for graphs with structures, combinatorial optimization, network design, distributed computing, and algorithm engineering.