Colloquium - Structures in Algorithm Design: Power and Limits

April 6, 2020 - 4:00pm to 5:00pm
Zoom - See emails for details
Hung Le
University of Victoria

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 V. LeBio:

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.