Open Collections

Approximating spanners and distance oracles.

Banff International Research Station for Mathematical Innovation and Discovery

Despite significant recent progress on approximating graph spanners (subgraphs which approximately preserve distances), there are still several large gaps in our understanding. In this talk I will survey some recent results, with a focus on low-stretch spanners (from SODA '16) and on spanners with demands (from SODA '17). But I will mostly describe the gaps and open problems which remain, including open questions on the power of linear and semidefinite relaxations for these kinds of network design problems. I will also discuss some recent results on approximation algorithms for optimizing distance oracles (the natural data-structure version of spanners). I will discuss some preliminary results from ITCS '17, including an O(log n)-approximation for optimizing stretch-3 Thorup-Zwick distance oracles. Again, though, I will mostly focus on the many interesting open problems remaining in approximation algorithms for optimizing data structures. Joint work with Zeyu Zhang, Eden Chlamtac, Guy Kortsarz, and Bundit Laekhanukit.

Mathematics; Computer science; Operations research, mathematical programming; Theoretical computer science

video/mp4

Author affiliation: Johns Hopkins University

2018-05-15

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/65874

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/