Improved Approximation Algorithms for Prize Collecting Steiner Tree and TSP
Mohammad Hajiaghayi · 55:46 · Watch on YouTube
Mohammad Taghi Hajiaghayi explains the first approximation algorithm for the prize-collecting Steiner tree that breaks the factor of 2 in place since 1992, reaching about 1.992 by running Goemans–Williamson on discoun...