Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

Approximating Prize-Collecting Variants of TSP

T0 review · 3 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper gives a 2.097-approximation algorithm for prize-collecting ordered TSP and a 2.41-approximation for prize-collecting multi-path TSP.

desk verdict First constant-factor algorithms for two natural prize-collecting TSP variants, but a false lemma and a missing LP constraint need fixing before this is referee-ready. read the letter →

arxiv 2411.14994 v1 pith:KVI36QX4 submitted 2024-11-22 cs.DS

Morteza Alimi , Tobias Mömke , Michael Ruderer This is my paper · ORCID
classification cs.DS MSC 68W2590C27
keywords prize-collectingTSPorderedmulti-pathapproximationalgorithmlinearprogrammingrelaxationtreesamplingparitycorrectionQ-join
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper introduces the prize-collecting ordered traveling salesman problem (PCOTSP), which generalizes both prize-collecting TSP and ordered TSP, and gives a 2.097-approximation algorithm for it. It also gives a 2.41-approximation algorithm for prize-collecting multi-path TSP, where a set of k terminal pairs must be connected by paths. The algorithms are LP-based: solve a fractional tour relaxation, sample random trees from the LP solution, then probabilistically prune low-value parts and pick up high-value omitted vertices before repairing parities. The result matters because it transfers two recent lines of TSP approximation work, pruning-based parity correction and forest-sampling pickup, into one unified framework with factors close to the best known for either special case.

What carries the argument

The load-bearing object is the ordered-tour LP relaxation (OLP), whose variables x_{i,e} and y_{i,v} describe a fractional stroll from terminal o_i to o_{i+1}. A decomposition lemma converts each fractional stroll into a distribution over trees with expected cost at most the LP cost and coverage at least y_v; this is what lets the algorithm sample trees. Two distribution functions, F_gamma(y) = (1 - $\alpha$(1-y))/(1 - $e^{{-y}}$) and F_sigma(y) = 1 - $\alpha$(1-y)/$e^{{-y}}$, set the pruning and pickup thresholds so that every vertex's expected penalty ratio stays at most $\alpha$. Parity correction is handled by a vector z = $\beta$ x + z_gamma + z_sigma that is shown to lie in the dominant of the odd-T''-join polytope, so its cost bounds the cheapest parity-correction join.

What would settle it

Find a PCOTSP instance on which Algorithm 1's total expected cost is strictly more than 2.097 times the true optimum, or exhibit an (OLP) integrality gap larger than 2.097; either would refute Theorem 1. A more direct check is the numerical inequality used in Lemma 8, since the monotonicity of g(y) at sigma_0 approximately 0.7818 is what makes the final factor hold.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: there is a 2.097-approximation algorithm for PCOTSP, and Theorem 2: there is a 2.41-approximation algorithm for PC-Multi-Path-TSP. For PCOTSP, the algorithm solves the ordered-tour LP relaxation, splits off vertices with low fractional value y_v, samples one tree per terminal-to-terminal segment so that each vertex v is covered with probability at least 1-$e^{{-y_v}}$, prunes each sampled tree down to its core at a random threshold, picks up critical vertices with y_v above a second random threshold by buying a rooted spanning forest, and then adds a cheapest odd-degree join. The expected tour cost and expected penalty are each bounded against the LP optimum, and the worst-case ratio is minimized at $\alpha$ = 2.097. For the multi-path version, two algorithms are combined, one that doubles sampled trees and adds direct terminal edges and one that samples a single PCTSP tree and doubles it, so the combined guarantee is 2.41.

Load-bearing premise

The analysis assumes the LP solution's vertex values y_v never exceed 1, so they act as probabilities and the penalty term pi_v(1-y_v) is nonnegative; the paper's displayed LP states only y >= 0 and never adds y_v <= 1.

Editorial extensions

If this is right

  • If the algorithm is correct, PCOTSP inherits the best known approximation guarantees of both special cases: k = 1 reduces to PCTSP and infinite penalties reduce to OTSP.
  • The cycle-versus-tree decomposition of the sampled structure shows that a cheap terminal cycle and an expensive terminal cycle are each useful: the first feeds the simple algorithm, the second makes parity correction cheaper.
  • The 2.41-approximation gives the first prize-collecting extension of Multi-Path-TSP; in the no-penalty limit it reproduces the earlier 2.367 factor given by the underlying Multi-Path-TSP approach.
  • The analysis identifies a single parameter alpha that balances penalties, pickup, and parity-correction costs; running the algorithm with alpha = 2.097 and the current best PCTSP factor 1.599 yields the stated bound.
  • The paper's discussion suggests that a factor of 2 or below for PCOTSP would require improving either PCTSP or OTSP techniques.
  • The paper's discussion suggests that a factor of 2 or below for PCOTSP would require improving either PCTSP or OTSP techniques.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The penalty-ratio balancing view, paying down a vertex's LP penalty either by connecting it up or by using its slack to subsidize pruning, could be applied to other prize-collecting connectivity problems wherever a fractional coverage y_v is available.
  • Since the displayed LP omits the constraint y_v <= 1, a reader implementing the algorithm should add it; with y_v unrestricted the penalty term pi_v(1 - y_v) can go negative and the sampling probabilities in the tree-decomposition lemma are undefined.
  • A natural testable extension is to replace the two fixed threshold distributions with per-instance optimized distributions; the paper's single-parameter tuning suggests that slack may remain in the analysis.
  • The integrality gap of the OLP is not computed; if it were later shown to exceed 2.097, the analysis would need a different LP, while a smaller gap could make the same framework tunable below 2.097.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper presents approximation algorithms for two prize-collecting generalizations of TSP: Prize-collecting Ordered TSP (PCOTSP) and Prize-collecting Multi-Path TSP. For PCOTSP the authors give a 2.097-approximation (Theorem 1), and for PC-Multi-Path-TSP a 2.41-approximation (Theorem 2). The approach solves an LP relaxation, samples trees via the Bang-Jensen--Frank--Jackson / Post--Swamy decomposition, prunes low-connectivity parts with a random threshold, probabilistically picks up high-y vertices with a second random threshold, and corrects parities with a Q-join. The analysis splits vertices according to their fractional y-values, bounds penalty ratios by α, and bounds the expected tour cost by combining the sampled-tree cost, the pickup forest cost, and the parity-correction cost, with the constant α tuned numerically to about 2.0969. The Multi-Path result combines two algorithms, one based on doubled sampled trees and one based on a contracted PCTSP tree plus direct terminal edges.

Significance. If the technical gaps are repaired, the paper would be a solid contribution: it is the first approximation below 2.1 for PCOTSP and gives a new bound for PC-Multi-Path-TSP, combining and extending the pruning ideas of [BKN24] with the pickup ideas of [BFMS25]. The numerical optimization is honest: the parameter α is chosen to minimize the derived closed-form bound, not fitted to instances, and the same holds for σ0′ in the Multi-Path section. The reliance on external theorems (Lemma 2, Theorem 3) is clearly stated, and the sampling view of penalty ratios is a useful conceptual framing. However, the current manuscript contains a false monotonicity lemma in the core tour-cost analysis and omits a necessary upper-bound constraint in the LP, so the main theorems are not yet established as written.

major comments (3)
  1. [Section 2.1, OLP formulation] The displayed s-t-stroll relaxation and the resulting OLP state only x, y ≥ 0 and do not include the constraint y_v ≤ 1. This is load-bearing: the objective contains π_v(1 − y_v), which becomes arbitrarily negative if y_v can grow, so the LP is unbounded below unless the upper bound is imposed. Moreover, Lemma 2 is used to treat y_v as a sampling probability, and Lemma 4 uses the inequality Pr[v ∉ T_i] ≤ 1 − y_{i,v}, which requires y_{i,v} ≤ 1. The fix is straightforward: add 0 ≤ y_v ≤ 1 (for each component y_{i,v}) to the relaxation, but it must be stated explicitly.
  2. [Section 3.3, Lemma 8] Lemma 8 is false as stated. For σ0 = 0.3, we have α = e^{−σ0}/(1−σ0) ≈ 1.05831, θ = 1 − 1/α ≈ 0.05510, β = 1/(3σ0 − θ) ≈ 1.18357, and direct evaluation gives g(0.2) ≈ 1.2915 > g(0.3) ≈ 1.2899. Thus g is not maximized at y = σ0 over [θ, σ0]. The proof claims that h(σ0) = α(1 − βσ0) − β is monotonically decreasing for σ0 > 0, but h(0.3) < 0 while h(0.78) > 0, so this monotonicity claim is also false. Since Lemma 8 is used in Eq. (4) of Lemma 7 to replace each g(η_i) by g(σ0), the tour-cost bound in Lemma 7 is not proved for the stated range. The final parameter value σ0 ≈ 0.7818 appears to lie in a range where the conclusion may hold, so the gap is likely repairable, but the lemma statement and proof must be corrected before Theorem 1 is established.
  3. [Section 3.3, Lemma 7 and Eq. (4)] Even if Lemma 8 is repaired, the current proof of Lemma 7 contains a notational error in the first displayed equality: the term c(R′) should be the expectation E[c(R′_π)] over the sampled trees, and the index in g(η_j) inside the sum should be g(η_i) to match the layer index. This is local, but it makes the layer argument harder to verify and should be fixed together with Lemma 8.
minor comments (4)
  1. [Section 3.3, Theorem 3] The statement of Theorem 3 says 'Pr[v ̸∈ S] ≤ ρ for each v ∈ X', but S is defined as a subset of U \ X. The quantifier should presumably be over v ∈ U \ X, which is how Lemma 9 applies it; as written, the theorem is vacuous or misstated.
  2. [Section 3.3, proof of Lemma 8] The displayed derivative 'dσ0/dt h(σ0)' appears to mix σ and σ0 and should read dh/dσ0; the expression as printed is not dimensionally consistent and cannot be checked as a derivative with respect to σ0.
  3. [Section 3.3, final bound of Lemma 7] The expression '2 + ˆα − α − (2 + 2 ˆα)βσ0 + 2αβσ0' is algebraically consistent with the preceding line, but the notation should be clarified: the term c(x) is used both for the split-off LP cost and for the original x* cost; the paper should state explicitly that c(x) ≤ c(x*) after splitting off.
  4. [Section 4, Algorithm B] The description 'Contract all 2k terminals into one mega-vertex w ... solve the PCTSP LP for this instance, and sample a tree T from the solution' is ambiguous: after contraction the terminal vertices are not present individually, so it is not immediate how the sampled tree is interpreted in the original graph or how adding the k edges {s_i, t_i} yields the claimed paths. Please clarify the contraction/uncontraction step and the exact edge set of H_B.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the approximation factors are derived from external LP-sampling and bridge-lemma results plus a parameter optimization, not from fitting the answer.

full rationale

The PCOTSP proof is a standard LP-based approximation analysis that invokes Lemma 2 (tree sampling from [BKN24], following [BJFJ95] and [PS15]) and Theorem 3 (the bridge lemma from [BFMS25]) as black-box external results. Neither statement contains the target 2.097 or 2.41 approximation factors, and the target theorems are not obtained by renaming those results. Although [BFMS25] shares an author with the present paper, it is an accepted external SODA 2025 publication with an independent proof, and it is used only for a general stochastic-forest lemma and algorithmic components; under the reviewing rules this counts as real evidence and does not raise the circularity score. The distributions F_sigma and F_gamma are chosen so that each vertex's expected penalty ratio is exactly alpha; this is an algorithmic design choice that makes Lemma 3 true, not a fitted value masquerading as a prediction. The final constant alpha = 2.097 is obtained by minimizing the proven worst-case bound max(alpha, f(alpha, alpha_hat)) with the external alpha_hat = 1.599, which is a legitimate optimization over a proved inequality rather than an answer-equivalent fit. The case distinction using the simple algorithm from Section 2 is a standard disjunction: if the terminal cycle is short, the simple algorithm suffices; otherwise the main analysis uses the lower bound on the cycle. The skeptical objection that Lemma 8 is false for sigma0 = 0.3 is a correctness gap in a technical lemma, not a circularity, because the lemma's bound does not assume its own conclusion. No derivation step in the paper reduces by construction to its own inputs.

Assumptions & free parameters 2 free parameters · 6 assumptions · 0 invented entities

The proof leans on several cited decomposition and forest-sampling theorems rather than proving them. The most fragile input is the implicit bound 0 ≤ y_v ≤ 1, which the displayed LP omits. If that bound is added and the quantifier in Theorem 3 is corrected, the remaining derivation is a self-contained optimization over the single parameter alpha.

free parameters (2)
  • alpha = 2.097
    Target approximation factor for PCOTSP. Chosen as the minimizer of max(alpha, f(alpha, alpha_hat)) in the derived bound, not fitted to data.
  • sigma_prime_0 = 0.892769
    Balance point for PC-Multi-Path-TSP between Algorithm A and Algorithm B bounds, derived from minimizing max(2+e^{-sigma'}, (1+e^{-sigma'}/(1-sigma'))/2).
assumptions (6)
  • standard math Lemma 2 tree decomposition: a feasible s-t stroll LP solution can be decomposed into trees with expected edge cost at most c(x) and vertex coverage at least y_v.
    Quoted from BKN24, based on Bang-Jensen-Frank-Jackson and Post-Swamy; used in Sections 2.3 and 4 without proof.
  • standard math Lemma 1 splitting-off: vertices with small y can be removed from an LP solution without increasing c(x) and with unchanged y for remaining vertices.
    Quoted from BKN24; used before sampling in Algorithm 1.
  • standard math Theorem 3 stochastic forest bound, as intended: if each vertex in U\X is missed with probability at most rho, then the expected optimal (X∪S)-rooted forest cost is at most rho times the X-rooted forest cost.
    Quoted from BFMS25. As printed it has the wrong quantifier over X instead of U\X; the application in Lemma 9 uses the corrected version.
  • domain assumption LP variables satisfy 0 ≤ y_v ≤ 1.
    Not stated in the OLP display but required for Lemma 2 and for the penalty term to be nonnegative; without it the LP can be unbounded below.
  • domain assumption The current best PCTSP approximation has ratio alpha_hat = 1.599 (BKN24).
    Used in the simple cycle-combining algorithm and in Lemma 7 to lower-bound the terminal cycle length.
  • domain assumption Terminals in PCOTSP are mandatory, i.e., they carry infinite penalty.
    The definition is ambiguous, but the LP forces y_o = 1 and Section 2.2 states all terminals have infinite penalty.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Approximating Prize-Collecting Variants of TSP." pith.science (2026). https://pith.science/paper/KVI36QX4

@misc{pith2026241114994,
  author       = {Pith},
  title        = {Pith review of: Approximating Prize-Collecting Variants of TSP},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KVI36QX4}},
  note         = {Machine review of arXiv:2411.14994}
}
abstract

We present an approximation algorithm for the Prize-collecting Ordered Traveling Salesman Problem (PCOTSP), which simultaneously generalizes the Prize-collecting TSP and the Ordered TSP. The Prize-collecting TSP is well-studied and has a long history, with the current best approximation factor slightly below $1.6$, shown by Blauth, Klein and N\"agele [IPCO 2024]. The best approximation ratio for Ordered TSP is $\frac{3}{2}+\frac{1}{e}$, presented by B\"{o}hm, Friggstad, M\"{o}mke, Spoerhase [SODA 2025] and Armbruster, Mnich, N\"{a}gele [Approx 2024]. The former also present a factor 2.2131 approximation algorithm for Multi-Path-TSP. By carefully tuning the techniques of the latest results on the aforementioned problems and leveraging the unique properties of our problem, we present a 2.097-approximation algorithm for PCOTSP. A key idea in our result is to first sample a set of trees, and then probabilistically pick up some vertices, while using the pruning ideas of Blauth, Klein, N\"{a}gele [IPCO 2024] on other vertices to get cheaper parity correction; the sampling probability and the penalty paid by the LP playing a crucial part in both cases. A straightforward adaptation of the aforementioned pruning ideas would only give minuscule improvements over standard parity correction methods. Instead, we use the specific characteristics of our problem together with properties gained from running a simple combinatorial algorithm to bring the approximation factor below 2.1. Our techniques extend to Prize-collecting Multi-Path TSP, building on results from B\"{o}hm, Friggstad, M\"{o}mke, Spoerhase [SODA 2025], leading to a 2.41-approximation.

Figures

Figures reproduced from arXiv: 2411.14994 by the authors.

Figure 1
Figure 1. (a) The graph T ′′ after pruning and picking up critical vertices. The terminals in O are drawn as black rectangles. The cycle C is depicted in red, the surviving edges of R are drawn in black and edges in FP in green. The greyed out vertices and edges do not belong to T ′′. They have either been pruned (the dashed vertices and edges), not sampled, or split off. (b) The same graph T ′′ with the various cuts that are… view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Approximating Graphic Multi-Path TSP and Graphic Ordered TSP

    cs.DS 2025-08 accept novelty 7.0 of 10

    Graphic Multi-Path TSP has a 2-approximation and LP integrality gap at most 2; Graphic Ordered TSP has a 1.791-approximation.

Reference graph

Works this paper leans on

19 extracted references · 17 canonical work pages · cited by 1 Pith paper

  1. [1]

    Improved approximation algorithms for prize-collecting S teiner tree and TSP

    Aaron Archer, MohammadHossein Bateni, MohammadTaghi Hajiaghayi, and Howard Karloff. Improved approximation algorithms for prize-collecting S teiner tree and TSP . SIAM journal on computing , 40(2):309--332, 2011

    work page 2011

  2. [2]

    2-approximation for prize-collecting steiner forest

    Ali Ahmadi, Iman Gholami, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, and Mohammad Mahdavi. 2-approximation for prize-collecting steiner forest. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 669--693. SIAM, 2024

    work page 2024

  3. [3]

    Prize-collecting steiner tree: A 1.79 approximation

    Ali Ahmadi, Iman Gholami, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, and Mohammad Mahdavi. Prize-collecting steiner tree: A 1.79 approximation. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 1641--1652, 2024

    work page 2024

  4. [4]

    A (3/2+ 1/e)-approximation algorithm for ordered TSP

    Susanne Armbruster, Matthias Mnich, and Martin N \"a gele. A (3/2+ 1/e)-approximation algorithm for ordered TSP . In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024) . Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2024

    work page 2024

  5. [5]

    o hm, Zachary Friggstad, Tobias M \

    Martin B \"o hm, Zachary Friggstad, Tobias M \"o mke, and Joachim Spoerhase. Approximating traveling salesman problems using a bridge lemma. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) . SIAM, 2025. To appear

    work page 2025

  6. [6]

    A note on the prize collecting traveling salesman problem

    Daniel Bienstock, Michel X Goemans, David Simchi-Levi, and David Williamson. A note on the prize collecting traveling salesman problem. Mathematical programming , 59(1):413--420, 1993

    work page 1993

  7. [7]

    On the approximation hardness of some generalizations of TSP

    Hans-Joachim B \"o ckenhauer, Juraj Hromkovi c , Joachim Kneis, and Joachim Kupke. On the approximation hardness of some generalizations of TSP . In Algorithm Theory--SWAT 2006: 10th Scandinavian Workshop on Algorithm Theory, Riga, Latvia, July 6-8, 2006. Proceedings 10 , pages 184--195. Springer, 2006

    work page 2006

  8. [8]

    Preserving and increasing local edge-connectivity in mixed graphs

    J rgen Bang-Jensen, Andr \'a s Frank, and Bill Jackson. Preserving and increasing local edge-connectivity in mixed graphs. SIAM Journal on Discrete Mathematics , 8(2):155--178, 1995

    work page 1995

Show all 19 references
  1. [9]

    A better-than-1.6-approximation for prize-collecting TSP

    Jannis Blauth, Nathan Klein, and Martin N \"a gele. A better-than-1.6-approximation for prize-collecting TSP . In International Conference on Integer Programming and Combinatorial Optimization , pages 28--42. Springer, 2024

    2024

  2. [10]

    o ckenhauer, Tobias M \

    Hans - Joachim B \" o ckenhauer, Tobias M \" o mke, and Monika Steinov \' a . Improved approximations for TSP with simple precedence constraints. J. Discrete Algorithms , 21:32--40, 2013

    2013

  3. [11]

    An improved approximation guarantee for prize-collecting TSP

    Jannis Blauth and Martin N \"a gele. An improved approximation guarantee for prize-collecting TSP . In Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages 1848--1861, 2023

    2023

  4. [12]

    Worst-case analysis of a new heuristic for the travelling salesman problem

    Nicos Christofides. Worst-case analysis of a new heuristic for the travelling salesman problem. Operations Research Forum , 3(1):20, 2022

    2022

  5. [13]

    Combining approximation algorithms for the prize-collecting TSP

    Michel X Goemans. Combining approximation algorithms for the prize-collecting TSP . arXiv preprint arXiv:0910.0553 , 2009

    2009 arXiv

  6. [14]

    A general approximation technique for constrained forest problems

    Michel X Goemans and David P Williamson. A general approximation technique for constrained forest problems. SIAM Journal on Computing , 24(2):296--317, 1995

    1995

  7. [15]

    A (slightly) improved approximation algorithm for metric TSP

    Anna R Karlin, Nathan Klein, and Shayan Oveis Gharan . A (slightly) improved approximation algorithm for metric TSP . In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages 32--45, 2021

    2021

  8. [16]

    Linear programming-based approximation algorithms for multi-vehicle minimum latency problems (extended abstract)

    Ian Post and Chaitanya Swamy. Linear programming-based approximation algorithms for multi-vehicle minimum latency problems (extended abstract). In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, U...

    2015

  9. [17]

    Some extremal bypasses in graphs [in russian]

    AI Serdjukov. Some extremal bypasses in graphs [in russian]. Upravlyaemye Sistemy , 17(89):76--79, 1978

    1978

  10. [18]

    Approximation Algorithms for Traveling Salesman Problems

    Vera Traub and Jens Vygen. Approximation Algorithms for Traveling Salesman Problems . Cambridge University Press, 2024

    2024

  11. [19]

    Reducing path TSP to TSP

    Vera Traub, Jens Vygen, and Rico Zenklusen. Reducing path TSP to TSP . In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages 14--27, 2020

    2020

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.