A Slightly Improved Approximation Algorithm for Metric TSP

A Slightly Improved Approximation Algorithm for Metric TSP

Simons Institute via YouTube Direct link

Why 2-uniform trees may help

7 of 21

7 of 21

Why 2-uniform trees may help

Class Central Classrooms beta

YouTube videos curated by Class Central.

Classroom Contents

A Slightly Improved Approximation Algorithm for Metric TSP

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

  1. 1 Intro
  2. 2 Metric TSP
  3. 3 Christofides' Algorithm
  4. 4 Approximation algorithms
  5. 5 Background #2: 2-uniform spanning trees
  6. 6 Algorithm we study
  7. 7 Why 2-uniform trees may help
  8. 8 Concentration property
  9. 9 A feasible solution
  10. 10 Applying a small perturbation
  11. 11 Cuts of interest
  12. 12 Stars have no even near min cuts
  13. 13 Degree cut case
  14. 14 Dream of induction
  15. 15 Example hierarchy
  16. 16 Increasing slack
  17. 17 Overall approach
  18. 18 Using probabilistic tool #1
  19. 19 Using probabilistic tool #2
  20. 20 Analysis
  21. 21 Next steps for polynomial geometers

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.