{"id":"4860fa71-8a4c-4221-ba37-d94c7c4d34b5","arxiv_id":"2411.14994","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"The paper gives a 2.097-approximation for Prize-Collecting Ordered TSP and a 2.41-approximation for Prize-Collecting Multi-Path TSP.","lead":"This paper introduces approximation algorithms for two new prize-collecting versions of TSP: one with a required ordering of terminals and optional other vertices, and one with multiple required paths. The algorithms achieve constant worst-case factors of 2.097 and 2.41, extending existing PCTSP and OTSP techniques.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 8 is false as stated: for σ0=0.3, g(y) has an interior maximum, so the proof of the 2.097 tour-cost bound has a gap.","rationale":"I read the paper as claiming a 2.097-approximation for PCOTSP via the OLP, sampling/pruning/pickup framework, and a 2.41-approximation for PC-Multi-Path-TSP. The central proof of the PCOTSP ratio is Lemma 7, and Lemma 7 invokes Lemma 8 to replace each layer coefficient g(η_i) by g(σ0). My independent check found that Lemma 8 is not true in the asserted parameter range: σ0=0.3 gives g(0.2)>g(0.3), and the accompanying monotonicity claim for h(σ0) is also false (h(0.3)<0, h(0.78)>0). This is an internal inconsistency, not a disagreement with consensus. It is load-bearing because the displayed proof of the tour-cost bound is invalid as written. It is likely fixable: for the numerical value σ0≈0.7818 used in the paper, a direct grid evaluation indicates the maximum of g is still at y=σ0, and h(σ0)>0, so the intended inequality survives after the lemma is restated for the actually used parameter range. The reader's weakest assumption (missing y_v≤1 in OLP) is also valid and should be fixed, but it is a different concern. Since both issues are repair-ready rather than contradictions of the central construction, I would keep the CONDITIONAL verdict; the paper should not be accepted before the lemma statement/proof and the LP constraint are corrected.","tokens_in":15504,"tokens_out":46849,"duration_ms":428067,"concrete_test":"Run the numerical evaluation of Lemma 8 with σ0=0.3: compute α=e^{-0.3}/0.7, θ=1−1/α, β=1/(3σ0−θ), Fγ(y)=(1−α(1−y))/(1−e^{-y}), and g(y)=Fγ(y)(2−2βy) at y=0.2 and y=0.3. If g(0.2)>g(0.3), the lemma as stated is false.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing gap is in Section 3.3, Lemma 8. The lemma claims that for every 0<σ0≤0.8, the function g(y)=Fγ(y)(2−2βy) with Fγ(y)=(1−α(1−y))/(1−e^{-y}), α=e^{-σ0}/(1−σ0), θ=1−1/α, β=1/(3σ0−θ), is maximized on [θ,σ0] at y=σ0. This is false. For σ0=0.3, α≈1.05831, θ≈0.05510, β≈1.18357, and direct evaluation gives g(0.2)≈1.2915 > g(0.3)≈1.2899, so the maximum is interior. The proof asserts h(σ0)=α(1−βσ0)−β is decreasing with a root above 0.8, but h(0.3)<0 while h(0.78)>0, so h is not decreasing and has a root near 0.5. Lemma 8 is used in Lemma 7 to bound the layered tree-edge contribution by g(σ0)c(R); without a valid bound, the 2.097 tour-cost inequality is unproved. For the actual σ0≈0.7818 the conclusion does appear to hold numerically, so the gap is fixable by restricting the lemma to σ0≥0.5 and checking h>0 for the chosen α, but the manuscript's statement as written is false.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":15854,"tokens_out":8203,"duration_ms":83877,"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":[{"comment":"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.","section":"Section 2.1, OLP formulation"},{"comment":"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.","section":"Section 3.3, Lemma 8"},{"comment":"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.","section":"Section 3.3, Lemma 7 and Eq. (4)"}],"minor_comments":[{"comment":"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.","section":"Section 3.3, Theorem 3"},{"comment":"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.","section":"Section 3.3, proof of Lemma 8"},{"comment":"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.","section":"Section 3.3, final bound of Lemma 7"},{"comment":"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.","section":"Section 4, Algorithm B"}],"recommendation":"major_revision","confidential_remarks":"The central claim is plausible and the numerical value α ≈ 2.0969 is consistent with the closed-form expression, but the false Lemma 8 is a load-bearing gap in the current write-up and the missing y_v ≤ 1 constraint is a genuine formulation error. Both appear fixable within the scope of the manuscript, so I recommend major revision rather than rejection. The authors should also double-check the statement of Theorem 3 and the description of Algorithm B."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, the good news: PCOTSP and PC-Multi-Path-TSP are natural problems that hadn't been defined before, and the paper gives the first constant-factor algorithms for them (2.097 and 2.41). The key move—sampling trees from the LP, probabilistically picking up vertices with high y-value, and pruning the rest using a tuned random threshold—is a genuine adaptation of BKN24 and BFMS25, and the way the simple cycle-through-terminals algorithm is used to get slack for parity correction is clever. The LP penalty-ratio argument in Section 3.1 is coherent, and the numerical optimization of alpha checks out.\n\nThe soft spots are real but mostly presentation. The displayed OLP omits y_v <= 1; without it the penalty term can go negative and Lemma 2 cannot turn y-values into sampling probabilities. Adding the bound is the obvious fix. Theorem 3 is misstated—the probability condition should be on vertices in U \\ X, not X—and as printed it makes the proof of Lemma 9 confusing.\n\nThe bigger issue is Lemma 8. The lemma as stated is false: for sigma0 = 0.3, g(y) has an interior maximum (g(0.2) ≈ 1.2915 vs g(0.3) ≈ 1.2899), and the proof's claim that h(sigma0) is decreasing with a root above 0.8 is wrong—h crosses zero near sigma0 = 0.5. The paper actually uses sigma0 ≈ 0.7818, which is in the safe regime, so the theorem probably survives once the lemma is restricted to sigma0 >= 0.5 and the derivative argument is corrected. But the manuscript currently asserts a false statement in a load-bearing place, and a referee will need the authors to fix this before the 2.097 claim is established.\n\nThe integral bounds in Lemmas 9 and 10 are consistent, the fixed point alpha ≈ 2.0969 checks out, and the citation pattern is clean: the reliance on BFMS25 is an external published theorem, not self-citation of the target result.\n\nBottom line: this is a solid contribution to the approximation-algorithms subfield, worth a serious referee, and likely to become a standard baseline for these two problems after revision. I would send it to review, but with a clear request to repair Lemma 8, add the missing LP bound, and restate Theorem 3.","headline":"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.","tokens_in":16354,"tokens_out":7716,"would_cite":true,"duration_ms":67187,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25","90C27"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper gives a 2.097-approximation algorithm for prize-collecting ordered TSP and a 2.41-approximation for prize-collecting multi-path TSP.","keywords":["prize-collecting TSP","ordered TSP","multi-path TSP","approximation algorithm","linear programming relaxation","tree sampling","parity correction","Q-join"],"falsifier":"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.","tokens_in":15335,"feed_emoji":"🗺️","tokens_out":5651,"duration_ms":55001,"temperature":0.7,"pith_summary":"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.","feed_headline":"New 2.097-approximation algorithm for prize-collecting ordered TSP","feed_subtitle":"Same method gives a 2.41-approximation for the multi-path version, unifying recent PCTSP and OTSP techniques.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Provides the splitting-off lemma, the tree-sampling lemma, and the pruning and parity-correction analysis that Algorithm 1 adapts to the ordered setting.","marker":"[BKN24]"},{"why":"Supplies the rooted-spanning-forest pickup theorem and the two-algorithm combination for Multi-Path-TSP on which the PC-Multi-Path result builds.","marker":"[BFMS25]"},{"why":"Gives the edge-connectivity decomposition that underlies the tree-sampling lemma.","marker":"[BJFJ95]"},{"why":"Shows the decomposition can be computed in polynomial time, making the sampling step algorithmic.","marker":"[PS15]"},{"why":"Provides the simple terminal-cycle-plus-TSP algorithm whose cycle-cost assumption is used in the parity-correction bound.","marker":"[BHKK06]"}],"fun_headline_variants":["2.097 approximation for prize-collecting ordered TSP","Prize-collecting ordered TSP: 2.097 approximation","New bound for prize-collecting ordered TSP","2.097-approx algorithm for PCOTSP"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["2.097 approximation for prize-collecting ordered TSP","Prize-collecting ordered TSP: 2.097 approximation","New bound for prize-collecting ordered TSP","2.097-approx algorithm for PCOTSP"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000792,"raw_usage":{"total_tokens":3585,"prompt_tokens":1136,"completion_tokens":2449,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":752,"completion_tokens_details":{"reasoning_tokens":2383}},"tokens_in":752,"tokens_out":2449,"duration_ms":18307,"temperature":1.0,"reasoning_tokens":2383,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T14:42:16.359961+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}