Structures in Algorithm Design: Power and Limits

February 14, 2020 - 11:15am to 12:15pm
Hung Le
Affiliation: 
University of Victoria
Location: 
3-180 Keller Hall
Host: 
Ravi Janardan

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 < csciseminar@umn.edu >.