On Light Spanners, Low-Treewidth Embeddings and Efficient Traversing in Minor-Free Graphs

On Light Spanners, Low-Treewidth Embeddings and Efficient Traversing in Minor-Free Graphs

IEEE FOCS: Foundations of Computer Science via YouTube Direct link

Light Preservers from Local Spanners

10 of 16

10 of 16

Light Preservers from Local Spanners

Class Central Classrooms beta

YouTube videos curated by Class Central.

Classroom Contents

On Light Spanners, Low-Treewidth Embeddings and Efficient Traversing in Minor-Free Graphs

Automatically move to the next video in the Classroom when playback concludes

  1. 1 Intro
  2. 2 Capacitated Vehicle Routing (CVR)
  3. 3 "Approximable" Instances.
  4. 4 "Approximable" means
  5. 5 Results for Subset TSP
  6. 6 Two techniques to design a PTAS
  7. 7 PTAS from Light Preservers
  8. 8 PTAS from Low Treewdith Embedding
  9. 9 The Framework
  10. 10 Light Preservers from Local Spanners
  11. 11 The rest of the talk: find L-local spanners.
  12. 12 Planar graph + One Vortex and D = 0(L)
  13. 13 Removing Diameter Constraint
  14. 14 Planar graph + O(1) Vortices
  15. 15 Tree of Clique-sums of Nearly-embed. Graphs
  16. 16 Open problems

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.