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; the webgraph has 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. I also talk about the limits on the advantage we can gain by adopting these structural models. Finally, I will go through open problems and future work.
Bio: Hung Le is currently a Pacific Institute for the Mathematical Sciences (PIMS) postdoc at University of Victoria. He received a Ph.D. in Computer Science from Oregon State University (2013-2018) 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.
*CSE Faculty may sign up for an appintment to meet with Hung Le at the following link: Appointment Sign Up Sheet.
All other scheduling inquiries may be sent to < email@example.com >.