"Approximating the Prize-Collecting Traveling Salesman Problem" by Associate Professor Dr. Brian Dean, School of Computing, Clemson University.
Abstract: Optimal trick-or-treating on Halloween can be quite a challenge from an algorithmic perspective -- not only must you find a minimum-length tour of a set of houses (the infamous NP-hard traveling salesman problem), but you may want to only include in this tour houses that are giving away the best candy. This leads to an even more challenging variant of the traveling salesman problem known as the "prize collecting" TSP, where it is not necessary to visit every node, but you receive a reward for those nodes you do visit (or equivalently, a penalty for unvisited nodes). The prize-collecting TSP has received considerable attention in the literature. In this seminar, I'll discuss the very first approximation algorithm proposed for it (due to Bienstock, Goemans, Simchi-Levi, and Williamson), which comes within a factor of 2.5 of an optimal solution.
No recent activity