Combining Approximation Algorithms for the Prize-Collecting TSP

L.A. Wolsey, “Heuristic analysis, linear programming and branch-and-bound”, Mathematical Programming Study

Original

1980

Earlier work this paper cites.

D.B. Shmoys and D.P. Williamson, “Analyzing the Held-Karp TSP lower bound: A monotonicity property with applications”, Operations Research Letters

1990

Earlier work this paper cites.

D. Bienstock, M.X. Goemans, D. Simchi-Levi and D. Williamson, “A Note on the Prize Collecting Traveling Salesman Problem”, Mathematical Programming

1993

Earlier work this paper cites.

M.X. Goemans and D.P. Williamson, “A General Approximation Technique for Constrained Forest Problems”, SIAM Journal on Computing

1995

Cited alongside, same era.

M.X. Goemans, “The Prize-Collecting TSP Revisited”, talk at the SIAM Disrete Mathematics conference, Toronto, Canada, July 1998

1998

Cited alongside, same era.

D.B. Shmoys. ”Using linear programming in the design and analysis of approximation algorithms: two illustrative problems”, in: Approximation Algorithms for Combinatorial Optimization, Lecture Notes in Computer Science 1444 (K. Jansen and J. Rolim, eds.), Springer, Berlin, 15–32, 1998

1998

Cited alongside, same era.

F.A. Chudak, T. Roughgarden, and D.P. Williamson, “Approximate k-MSTs and k-Steiner trees via the primal-dual method and Lagrangean relaxation”, Mathematical Programming

2004

Later among the works it cites.

A. Archer, M. Bateni, M. Hajiaghayi and H. Karloff, “Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP”, Proceedings of the 50th Annual Symposium on Foundations of Computer Science, 2009

2009

Closest in time.