A 3/2-Approximation for Prize-Collecting TSP and a Black-Box Reduction from TSP to PCTSP

Prize-Collecting TSP (PCTSP), introduced by Balas (1989), generalizes the metric traveling salesman problem: given a complete graph with metric edge costs, a root vertex, and nonnegative vertex penalties, one seeks a minimum-cost tour through any vertex set containing the root, paying the penalties of all vertices left out. The best known polynomial-time guarantee is the LP-relative 1.599-approximation of Blauth, Klein and Nägele (IPCO 2024; Mathematical Programming 2025), continuing the line 5/2 -> 2 -> 1.979 -> 1.914 -> 1.774. That paper explicitly poses the question studied here: does PCTSP admit an efficient algorithm matching the classical Christofides-Serdyukov $3/2$ guarantee for metric TSP — ideally as a black-box reduction turning any $\alpha$-approximation for TSP into an $\alpha$- (or $(\alpha+\varepsilon)$-)approximation for PCTSP, as Traub-Vygen-Zenklusen achieved for path TSP — with parity correction at expected cost $c^{\top}x/2$ identified as the sufficient sub-goal that would immediately give $3/2$? No improvement below 1.599, no $3/2$ result, no TSP-to-PCTSP reduction, and no separation of the natural PCTSP LP's integrality gap from the Held-Karp relaxation is known: the problem remains open.

Background

The metric traveling salesman problem (TSP) asks for a shortest closed tour visiting every vertex of a complete graph whose edge costs obey the triangle inequality. The classical algorithm of Christofides (1976) and Serdyukov (1987) computes a minimum spanning tree, adds a minimum-cost matching on the tree's odd-degree vertices — the standard "parity correction" step, more generally phrased as adding a minimum-cost $T$-join (a set of edges whose odd-degree vertices are exactly a prescribed set $T$) — and shortcuts the resulting Eulerian walk; it is a $3/2$-approximation, i.e., its tour costs at most $3/2$ times the optimum. Only in 2021-2023 was this ratio marginally beaten for metric TSP, to $3/2-\varepsilon$ with tiny $\varepsilon$ (Karlin-Klein-Oveis Gharan).

The prize-collecting TSP (PCTSP), introduced by Balas (1989), generalizes this setting: an instance is a complete graph with metric edge costs $c$, a distinguished root vertex $r$, and a nonnegative penalty $\pi_v$ for each vertex. A feasible solution is a tour through any vertex set containing $r$, and its cost is the length of the tour plus the penalties of all vertices not visited. PCTSP models routing with voluntary customers (skipping a customer costs $\pi_v$) and is the tour version of a large family of prize-collecting network design problems.

The dominant technique is rounding the natural linear programming (LP) relaxation, which extends the classical Held-Karp relaxation of TSP (the subtour relaxation) with a variable $y_v\in[0,1]$ expressing the extent to which $v$ is visited:

$\min\ \sum_{e\in E}c_e x_e+\sum_{v\in V}\pi_v(1-y_v)$

$x(\delta(v))=2y_v\ \ \forall v\in V\setminus\{r\},\qquad x(\delta(r))\le 2,\qquad x(\delta(S))\ge 2y_v\ \ \forall S\subseteq V\setminus\{r\},\ \forall v\in S,$

$y_r=1,\qquad x_e\ge 0,\qquad y_v\ge 0,$

where $\delta(S)$ denotes the set of edges with exactly one endpoint in $S$. An algorithm is LP-relative with ratio $\alpha$ if on every instance its output costs at most $\alpha$ times this LP's optimum; since the LP optimum lower-bounds the true optimum, this implies an ordinary (true) $\alpha$-approximation. The integrality gap of a relaxation — the worst-case ratio of true optimum to LP optimum — lower-bounds every LP-relative ratio; for the Held-Karp relaxation it lies between $4/3$ and $3/2-\varepsilon$, and its exact value is a famous open problem.

A useful structural fact (Blauth-Nägele 2023, via results on packing branchings, i.e., arborescences, in directed multigraphs) is that any solution $(x,y)$ of the PCTSP LP decomposes, in polynomial time, into a distribution over trees rooted at $r$ with expected edge cost at most $c^{\top}x$ and with each vertex $v$ appearing with probability exactly $y_v$. Algorithms then sample a tree, prune it, correct parity, and shortcut. The ratio history: Bienstock-Goemans-Simchi-Levi-Williamson (1993) obtained an LP-relative $5/2$ by threshold rounding (tour all vertices with $y_v\ge 3/5$ via Christofides-Serdyukov); Goemans-Williamson's (1995) primal-dual method gives $2$; Archer-Bateni-Hajiaghayi-Karloff (2011) combined both to roughly $1.979$ using a $3/2$ TSP algorithm as a black box; Goemans (2009) refined this to roughly $1.914$; Blauth-Nägele (2023) reached $1.774$; and Blauth-Klein-Nägele (arXiv 2023; IPCO 2024; Mathematical Programming 2025) introduced the prune-then-correct-parity scheme, first analyzed via the golden ratio $(1+\sqrt{5})/2\approx1.618$ and then refined to $1.599$ — the current best guarantee, and the source of the present open problem.

Why does the TSP analysis not simply transfer? For TSP, parity correction is cheap: for any tree from the LP support and any even set $Q$ of vertices, the point $x/2$ lies in the up-monotone hull of the $Q$-join polyhedron (the up-closure of the convex hull of $Q$-join incidence vectors), so a minimum $Q$-join costs at most $c^{\top}x/2$; together with the tree cost this yields exactly $3/2$. In the prize-collecting setting this containment fails, because the decomposition trees need not span all vertices and the LP solution is not Eulerian (vertex degrees are $2y_v$ with $y_v<1$ allowed). Blauth-Klein-Nägele write: "It is an intriguing question whether parity correction can be done at expected cost $c^{\top}x/2$. Such a result would immediately lead to a $3/2$-approximation algorithm for PCTSP." Their workaround prunes each sampled tree and pays for it with the ratio $1.599$; their analysis (Remark 9 of the journal version) cannot reach $1.59$ within their framework, though the algorithm's true worst-case guarantee may be lower.

The strongest conceivable positive answer mirrors a breakthrough for the path version of TSP: Traub-Vygen-Zenklusen (2022) reduced path TSP to TSP, converting any $\alpha$-approximation for TSP (as an unmodified black box) into an $(\alpha+\varepsilon)$-approximation for path TSP; Blauth-Klein-Nägele call the analogous black-box reduction from TSP to PCTSP "the ideal result". Relatedly, on the polyhedral side, prize-collecting aspects are known to strictly inflate LP gaps in some settings — the natural LP for prize-collecting Steiner forest has integrality gap at least $9/4$ while the Steiner forest relaxation's gap is $2$ — but no such separation is known between the PCTSP relaxation and the Held-Karp relaxation.

Problem Statement

Does there exist a polynomial-time algorithm for Prize-Collecting TSP (PCTSP) on metric instances — complete graph, metric edge costs, root vertex $r$, nonnegative vertex penalties $\pi_v$, objective $c(\text{tour})+\sum_{v\text{ not visited}}\pi_v$ — whose approximation guarantee matches that of metric TSP algorithms, i.e., a $3/2$-approximation (matching Christofides-Serdyukov), or even $3/2-\varepsilon$ (matching the current best TSP guarantee)? Blauth-Klein-Nägele pose this in two precise forms:

1. (LP-relative form) A polynomial-time algorithm whose output cost is at most $3/2$ times the optimum of the natural PCTSP LP relaxation stated in the Background, on every instance. Since the LP optimum lower-bounds the true optimum, this implies a true $3/2$-approximation; it is the benchmark under which the current best guarantee of $1.599$ is proved.

2. (Black-box reduction form, "the ideal result") An efficient transformation that, given any $\alpha$-approximation algorithm for metric TSP used as an unmodified black box, produces an $\alpha$-approximation for PCTSP — or an $(\alpha+\varepsilon)$-approximation for every fixed $\varepsilon>0$.

A sufficient sub-goal identified by the source: prove that, for trees drawn from the LP-solution decomposition, parity correction can be performed at expected cost at most $c^{\top}x/2$ in the prize-collecting setting; the source states that this would immediately yield a $3/2$-approximation algorithm. A negative resolution of form 1 — for example, an explicit family of metric PCTSP instances for which the natural LP's integrality gap provably exceeds $3/2$ — is an equally admissible answer for that form. The problem is settled by a correct algorithm and proof, a correct reduction, or a sound refutation of the corresponding form.

References

1. Jannis Blauth, Nathan Klein, Martin Nägele. "A Better-Than-1.6-Approximation for Prize-Collecting TSP." arXiv:2308.06254 (2023; v3 January 2025). DOI: 10.48550/arXiv.2308.06254. https://arxiv.org/abs/2308.06254. Conference version: Proceedings of IPCO 2024, LNCS, pp. 28-42, DOI: 10.1007/978-3-031-59835-7_3. Journal version: Mathematical Programming 216, pp. 87-109 (2025), DOI: 10.1007/s10107-025-02221-4.
2. Jannis Blauth, Martin Nägele. "An Improved Approximation Guarantee for Prize-Collecting TSP." Proceedings of STOC 2023, pp. 1848-1861. DOI: 10.1145/3564246.3585159; arXiv:2212.03776. https://arxiv.org/abs/2212.03776
3. Egon Balas. "The prize collecting traveling salesman problem." Networks 19(6), 1989, pp. 621-636. DOI: 10.1002/net.3230190602. https://doi.org/10.1002/net.3230190602
4. Daniel Bienstock, Michel X. Goemans, David Simchi-Levi, David P. Williamson. "A note on the prize collecting traveling salesman problem." Mathematical Programming 59, 1993, pp. 413-420. DOI: 10.1007/BF01581256. https://doi.org/10.1007/BF01581256
5. Michel X. Goemans, David P. Williamson. "A General Approximation Technique for Constrained Forest Problems." SIAM Journal on Computing 24(2), 1995, pp. 296-317. DOI: 10.1137/S0097539793242618. https://doi.org/10.1137/S0097539793242618
6. Aaron Archer, MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Howard Karloff. "Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP." SIAM Journal on Computing 40(2), 2011, pp. 309-332. DOI: 10.1137/090771429. https://doi.org/10.1137/090771429
7. Michel X. Goemans. "Combining Approximation Algorithms for the Prize-Collecting TSP." arXiv:0910.0553 (2009). https://arxiv.org/abs/0910.0553
8. Vera Traub, Jens Vygen, Rico Zenklusen. "Reducing Path TSP to TSP." SIAM Journal on Computing 51(3), 2022, pp. STOC20-24-STOC20-53. DOI: 10.1137/20M135594X. https://doi.org/10.1137/20M135594X
9. Anna Karlin, Nathan Klein, Shayan Oveis Gharan. "A (Slightly) Improved Approximation Algorithm for Metric TSP." Proceedings of STOC 2021. DOI: 10.1145/3406325.3451009. https://doi.org/10.1145/3406325.3451009
10. Anna Karlin, Nathan Klein, Shayan Oveis Gharan. "A Deterministic Better-than-3/2 Approximation Algorithm for Metric TSP." Proceedings of IPCO 2023, LNCS, pp. 261-274. DOI: 10.1007/978-3-031-32726-1_19. https://doi.org/10.1007/978-3-031-32726-1_19
11. René van Bevern, Viktoriia Slugina. "A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem." Historia Mathematica 53, 2020, pp. 118-127. DOI: 10.1016/j.hm.2020.04.003. https://doi.org/10.1016/j.hm.2020.04.003 (documents the Christofides 1976 and Serdyukov 1987 algorithms)
12. Jochen Könemann, Neil Olver, Kanstantsin Pashkovich, R. Ravi, Chaitanya Swamy, Jens Vygen. "On the Integrality Gap of the Prize-Collecting Steiner Forest LP." Proceedings of APPROX/RANDOM 2017, LIPIcs 81, pp. 17:1-17:13. DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.17. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.17
13. Ali Ahmadi, Iman Gholami, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, Mohammad Mahdavi. "Prize-Collecting Steiner Tree: A 1.79 Approximation." Proceedings of STOC 2024, pp. 1641-1652. DOI: 10.1145/3618260.3649789. https://doi.org/10.1145/3618260.3649789
14. Morteza Alimi, Tobias Mömke, Michael Ruderer. "Approximating Prize-Collecting Variants of TSP." arXiv:2411.14994 (2024). Conference version: MFCS 2025, LIPIcs, pp. 7:1-7:17, DOI: 10.4230/LIPIcs.MFCS.2025.7, https://doi.org/10.4230/LIPIcs.MFCS.2025.7. Preprint DOI: 10.48550/arXiv.2411.14994. https://arxiv.org/abs/2411.14994
15. Hong Li. "Reducing Prize-Collecting Stroll and Related Routing Problems to Prize-Collecting TSP." arXiv:2606.18157 (2026). DOI: 10.48550/arXiv.2606.18157. https://arxiv.org/abs/2606.18157
16. Hong Li, Jianping Li, Wei Li, Runtao Xie, Xiaoxiao Yang. "Approximation algorithms for the prize-collecting rural postman problem." arXiv:2605.24944 (2026). DOI: 10.48550/arXiv.2605.24944. https://arxiv.org/abs/2605.24944
17. Marek Karpinski, Michael Lampis, Richard Schmied. "New inapproximability bounds for TSP." Journal of Computer and System Sciences 81(8), 2015, pp. 1665-1677. DOI: 10.1016/j.jcss.2015.06.003. https://doi.org/10.1016/j.jcss.2015.06.003