Explore cutting-edge graph theory concepts in this 24-minute IEEE conference talk covering light spanners, low-treewidth embeddings, and efficient traversing in minor-free graphs. Delve into Capacitated Vehicle Routing, Subset TSP, and techniques for designing Polynomial-Time Approximation Schemes (PTAS). Learn about light preservers, local spanners, and their applications in planar graphs with vortices. Examine tree structures of clique-sums in nearly-embedded graphs and discover open problems in the field. Gain insights from researchers Vincent Cohen-Addad, Arnold Filtser, Philip N. Klein, and Hung Le as they present advanced algorithms and graph theory applications.
On Light Spanners, Low-Treewidth Embeddings and Efficient Traversing in Minor-Free Graphs
Overview
Syllabus
Intro
Capacitated Vehicle Routing (CVR)
"Approximable" Instances.
"Approximable" means
Results for Subset TSP
Two techniques to design a PTAS
PTAS from Light Preservers
PTAS from Low Treewdith Embedding
The Framework
Light Preservers from Local Spanners
The rest of the talk: find L-local spanners.
Planar graph + One Vortex and D = 0(L)
Removing Diameter Constraint
Planar graph + O(1) Vortices
Tree of Clique-sums of Nearly-embed. Graphs
Open problems
Taught by
IEEE FOCS: Foundations of Computer Science
