Friday Algorithms Seminar with Dr. Brian Dean, School of Computing, Clemson University

Friday, November 1, 2013 at 3:30pm to 4:30pm

McAdams Hall, 114 821 McMillan Rd., Clemson, SC 29634, USA

"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.

Event Type

Lectures, Seminars


School of Computing, College of Engineering, Computing and Applied Sciences

Target Audience

Students, Faculty

Contact Name:

Kris Coleman

Contact Phone:


Contact Email:

Recent Activity

People Going

Getting Here