Structures in Algorithm Design: Power and Limits

Abstract: 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 how to leverage the structures in solving three different algorithmic problems: constructing spanners, approximating the Traveling Salesperson Problem, and analyzing local search heuristics; and the limits on the advantage we can gain by adopting these structural models. Finally, I will talk about open problems and future work.

Bio: Hung Le is currently a Pacific Institute for the Mathematical Sciences (PIMS) postdoc at University of Victoria with Valerie King. He recieved 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.

A reception for attendees will be held at 3:30 in CS 150