BIRS Workshop Lecture Videos
Approximating spanners and distance oracles. Dinitz, Michael
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.
Item Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International