The Line Traveling Salesman and Repairman Problem with Collaboration

Finn S\"orensen; Julian Golak; Malte Fliedner

REVIEW 5 major objections 6 minor 16 references

The Line Traveling Salesman and Repairman Problem with Collaboration

T0 review · 5 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read The paper claims that allowing clients to move along the line toward the server produces a full complexity landscape for the Line Traveling Salesman and Repairman Problems, with linear and near-linear algorithms for fast-client variants…

desk verdict Solid complexity map for collaborative line routing, but the wait-free structural lemma has a sign error that currently undermines the main DPs. read the letter →

arxiv 2506.04127 v1 pith:VFYPZ3Q4 submitted 2025-06-04 cs.CC

Julian Golak , Finn Sörensen , Malte Fliedner This is my paper

classification cs.CC

keywords TravelingSalesmanProblemRepairmancollaborationrendezvouscomputationalcomplexityNP-completenessdynamicprogrammingscheduling

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

This paper extends two classic one-dimensional routing problems—the Line Traveling Salesman Problem (minimize the server's return time) and the Line Traveling Repairman Problem (minimize the sum of client completion times)—by allowing clients to move along the line toward the server. It tries to establish where collaboration makes these problems tractable and where it does not. On the tractable side, it gives linear-time algorithms for several variants with fast clients, and quadratic- and cubic-time dynamic programs plus a pseudo-polynomial dynamic program for slow-client deadline variants. On the hard side, it transfers known NP-hardness results to slow-client collaborative versions and proves that the feasibility problem with deadlines is strongly NP-complete for any positive client speed. Together these results draw a complexity landscape showing that collaboration can make previously hard problems easy, and previously easy feasibility problems hard.

What carries the argument

The load-bearing mechanism is the time-space trajectory of a server moving at unit speed on a line, paired with the rendezvous identity: when the server and a client at speed v move toward each other, the time until they meet is the current separation divided by 1+v. In the dynamic programs this identity lets one compute the next rendezvous from only the state value—the server's position and the client's position at the previous service time—once the solution is assumed to be wait-free and to have clients travelling without waiting. The DP state enumerates pendulum-like sequences that alternate between serving clients on the left and on the right, and the identity determines the transition costs; for the repairman objective time is added to the state, giving a pseudo-polynomial bound T = O(Σ|s(a)|).

What would settle it

Run a brute-force solver on all small instances with slow clients (say up to six clients), zero processing times, deadlines, and integer positions, and compare its true optimal makespan and sum-of-completion-times to the outputs of Algorithms 1 and 3; any mismatch would refute the claimed optimality. A sharper check is to search specifically for a feasible instance in which every optimal solution forces the server to wait or a client to wait before its rendezvous, since Lemmas 3 and 4 assert that no such instance exists.

Watch

Extended reading notes

Core claim

The paper's central claim is that introducing mobile, collaborating clients changes the complexity of line routing in both directions at once. For fast clients (v≥1), the server can always be routed as if the rendezvous happened at the origin: the paper proves O(n) and O(n log n) algorithms for release-time and time-window variants (Theorems 6 and 7). For slow clients (0<v<1) with deadlines, the paper proves that an optimal solution can be taken to be order-preserving, wait-free for the server, and to have clients that travel directly to their rendezvous without waiting, and builds optimal dynamic programs on this structure (Algorithms 1–3, Theorems 9, 10, and 14). In contrast, it shows that deciding whether any feasible schedule exists when deadlines are present is strongly NP-complete even for arbitrary small positive v (Theorem 17), via a reduction from 3-Partition. The result is a mapping of polynomial, pseudo-polynomial, and NP-complete cells of the collaborative LTSP and CLTRP landscape.

Load-bearing premise

The central algorithms for slow clients with deadlines assume that some optimal solution has a server that never waits and clients that never wait before their rendezvous; if that structural premise fails, the recurrence costs in the dynamic programs are not justified.

Editorial extensions

If this is right

Fast clients make the CLTSP solvable in linear time with only release times (Theorem 6) and in O(n log n) time with full time windows (Theorem 7), so allowing clients to move toward the server removes the hardness of the corresponding non-collaborative variants.
Slow clients with only deadlines admit polynomial algorithms for the CLTSP: O(n) for zero processing times with no time constraints (Theorem 5), O(n^2) with zero processing times and deadlines (Theorem 9), and O(n^3) with general processing times and no time constraints (Theorem 10).
The CLTRP with zero processing times, deadlines and slow clients admits a pseudo-polynomial O((T n)^2) algorithm, where T is bounded by a linear function of the input under unary encoding.
Slow-client collaborative versions inherit the NP-hardness of their non-collaborative counterparts: the CLTRP with release times is binary NP-hard, and the CLTSP with release times and general processing is binary NP-hard (Corollaries 15 and 16).
The feasibility problem with deadlines is strongly NP-complete for any positive client speed (Theorem 17), so moving clients can make even finding a feasible schedule intractable.

Reading between the lines

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

A consequence the authors leave implicit is that the same pendulum decomposition and closing-speed identity might extend to line problems with multiple servers, where each server's trajectory would be an independent pendulum and meetings would still be governed by the 1+v rendezvous formula.
The paper's transfer of hardness for arbitrarily slow clients, combined with Theorem 17's hardness for all positive speeds, points to a sharp regime transition: as client speed tends to zero collaboration cannot help asymptotically, yet any positive speed is enough to make deadline feasibility intractable; testing intermediate speeds on small instances could reveal whether this transition is genui
The authors pose but do not prove a wait-free conjecture for fast clients; if that conjecture is established, Algorithm 3 could plausibly be extended to give a pseudo-polynomial CLTRP for fast clients, a natural next step that the paper leaves open.

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.

Desk Editor's Note

read the letter

The paper is worth reading, but the core structural lemma has a concrete sign error that currently pulls the rug out from under the main algorithms. In Lemma 3 the new rendezvous is defined as x'_i = x_i + (s'(a) - x_{i-1})/(1+v). Since s'(a) ≥ x_{i-1}, the added term is nonnegative, so x'_i ≥ x_i, not x'_i ≤ x_i as the proof claims. The subsequent inequality uses x_i - x'_i ≥ 0, which is false, so the wait-free argument collapses. Lemma 4 inherits the problem, and the correctness proofs of Algorithms 1–3 (Theorems 9, 10, 14) rest on these lemmas. This is the load-bearing gap; if the wait-free property fails, the DPs only search a restricted class of solutions.

What the paper does well: it introduces a natural collaborative variant of line routing, produces a useful complexity map (Table 2), and transfers hardness results via a clean velocity-scaling argument in Section 5. The fast-client algorithms in Theorems 6 and 7 are genuinely clever, and the reduction from 3-Partition in Theorem 17 is convincing once you fix the obvious typo ("within 3m time units" should be "within m·B time units").

Other soft spots are minor by comparison. Theorem 6 claims an O(n) algorithm for release times and fast clients, but after moving all rendezvous to the origin you are left with a single-machine scheduling problem with release times; the proof only asserts the bound without giving the sorting or exchange argument. Lemma 8 also reads oddly, with a suspicious definition of the modified solution and an apparent confusion between s(a) and x(a). These are fixable in revision.

The citations look honest and relevant; the paper builds on the right prior work (Afrati, Tsitsiklis, Bock, Sitters) and does not overclaim novelty. If the authors repair the algebra in Lemmas 3–4 and fill the gap in Theorem 6, this becomes a solid contribution. As is, the paper should not be accepted without those repairs.

Who this is for: researchers working on routing with mobile agents or on line TSP variants. It would be a useful reading-group discussion, mostly for spotting how a small coordinate inconsistency can invalidate a DP correctness argument. I would not cite it in its current form, but I would send it to a serious referee: the model and results are plausible, the gap looks patchable, and the complexity map has value.

Referee Report

5 major / 6 minor

Summary. The paper introduces collaborative variants of the Line Traveling Salesman Problem (CLTSP) and the Line Traveling Repairman Problem (CLTRP), in which a single server and mobile clients on a line choose rendezvous positions and times. It claims a comprehensive complexity landscape: polynomial-time algorithms for several variants (Theorems 5, 6, 7, 9, 10), a pseudo-polynomial dynamic program for CLTRP with deadlines and slow clients (Theorem 14), and strong NP-completeness of the feasibility problem with deadlines for any client speed (Theorem 17). The algorithms are built on structural lemmas asserting the existence of optimal solutions that are order-preserving, wait-free for the server, and colliding for clients.

Significance. The model is a natural extension of classical line routing problems, and the paper attempts a systematic map of tractable and intractable cases, which would be a useful contribution if the proofs were correct. Several transfers of hardness from the literature are sensible, and the algorithms are concrete enough to be checked. However, the structural core of the paper is not established: Lemma 3 contains a concrete coordinate inconsistency, Lemma 8's strict inequality is an equality after substitution, and Theorem 6's O(n) claim is asserted without a specified scheduling algorithm. These are load-bearing issues for the main algorithmic results, so the significance is contingent on a successful repair.

major comments (5)

[Section 2, Lemma 3] Lemma 3 defines x'_i = x_i + (s'(a)-x_{i-1})/(1+v) after assuming s'(a) >= x_{i-1}. Hence x'_i >= x_i, not x'_i <= x_i as claimed. The proof then uses x_i - x'_i >= 0 and the strict inequality t'_i + (x_i - x'_i) + tau(a) < t_i + (x_i - x'_i)/v + tau(a), both of which require x_i - x'_i > 0; with the defined x'_i the difference is nonpositive, so the comparison collapses. Moreover, at time t'_i the client's position is (s'(a)+v x_{i-1})/(1+v), which is not equal to x'_i in general, so the proposed new rendezvous is not even on the client's trajectory. Since Lemma 4 and Algorithms 1-3 (Theorems 9, 10, 14) rely on the wait-free property, this is a load-bearing gap.
[Section 2, Lemma 8] Lemma 8 claims a strict inequality in the proof: t'(a)+(x'(a)-x(a))/v+tau(a) < (s(a)-x(a))/v+tau(a). But from the colliding-client relation s(a)=x'(a)+v t'(a)=x(a)+v t(a), we get (x'(a)-x(a))/v = t(a)-t'(a), so the left side equals c(a), not a smaller quantity. The construction of (t*,x*) also leaves all subsequent rendezvous unchanged even though after processing a the server is at x'(a) instead of x(a); reachability of later rendezvous is not shown. There is also a notational slip: the case distinction 'if a' in A' should read 'if a' in A''. Because Lemma 8 is the dominance argument cited in the correctness proofs of Theorems 9 and 10, those proofs are incomplete.
[Section 3, Theorem 6] Theorem 6 claims an O(n) algorithm for CLTSP with fast clients, release times, and general processing times. The proof invokes Lemma 4 to assume clients are colliding, but Lemma 4's proof depends on Lemma 3, which is stated for slow clients and deadlines; no colliding property is established for the fast-client release-time setting. Even if all rendezvous can be moved to the origin, the residual problem is single-machine scheduling with release times r(a)+|s(a)|/v and processing times tau(a); the proof does not specify an algorithm for this scheduling problem, and its optimal makespan is not trivially O(n) without sorting. In addition, the inequality c_{j-1}+|x_j| <= c_{j-1}+|x_j|+|x_j-x_{j-1}| <= t_j+|x_j| compares |x_j| with |x_{j-1}| without justification. Theorem 6 and its Table 2 entry are therefore unsupported as written.
[Section 5, Theorem 17] In the 3-Partition reduction, the proof asserts that the server must be free at the origin at times jB. This is not immediate, because a distant client with |s_{3m+j}|/v = jB can be met before time jB if the server leaves the origin toward it. The reduction needs an argument excluding such meetings; one is available (the 3m origin clients have total processing time mB and deadline mB, so any positive travel time away from the origin makes the instance infeasible), but the proof does not provide it. The phrase 'within 3m time units' should also be 'within mB time units'.
[Section 3, Theorem 5] Theorem 5 contains algebraic errors in the comparison of the two candidate orders. Using the paper's own formulas, x(r)-|x'(ell)| equals (1-v)(s(r)-s(ell))/(1+v)^2, not (3v+1)(s(ell)+s(r))/(1+v)^2. The displayed makespans Cmax(t,x)=t(ell)+|x(ell)| and Cmax(t',x')=t'(r)+|x'(r)| are also the wrong endpoints, since the last clients in the two solutions are r and ell respectively. The subsequent comparison t'(ell)-t(r) and x(r)-|x'(ell)| does correspond to the correct makespan difference, and the positivity conclusion can be recovered, so this is a repairable algebraic error, but the proof as printed is incorrect.

minor comments (6)

[Section 3, after Theorem 9] 'Consider the CSTP with general processing times' should read 'CLTSP'.
[Figure 3 caption] The caption says 'with time of the horizontal axis and time on the vertical axis'; the vertical axis should be space.
[References] Reference [6] lists 'Freeman, San Francisco, 1797'; the correct year is 1979.
[Section 2, Lemma 4] The statement of Lemma 4 is awkward: 'for all a in R ... otherwise' should state the L-case explicitly.
[Section 4, Theorem 14] The state space is O(T n^2), while the theorem states O((T n)^2); the latter is a valid upper bound for T>=1 but is unnecessarily loose, and the relation between the two bounds should be clarified.
[Section 3, Theorems 9 and 10] The correctness proofs say 'By lemma 8 ... the time at each state in the dynamic programming table is minimized' without formally connecting the dominance lemma to the recurrence and the pruning of states; this connection should be spelled out.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper's derivations are self-contained proof chains, not fitted inputs or self-citation loops.

full rationale

The paper's derivation chain is self-contained and does not exhibit any of the circularity patterns. The algorithms in Theorems 5, 6, 7, 9, 10, and 14 are justified by structural lemmas (Lemmas 1-4, 8, 11-13) that are stated and proven in the same paper; the lemmas are inputs to the proofs, not consequences of the algorithms. The hardness results in Theorem 17 and Corollaries 15-16 are obtained by standard reductions from 3-Partition and from prior cited LTSP/LTRP hardness results, which are external results rather than self-citations of the present authors. No parameter is fitted to data, no quantity is renamed as a prediction, no uniqueness theorem is imported from the authors' prior work, and no ansatz is smuggled in through a citation. The reader's noted algebraic error in Lemma 3 is a correctness gap in the proof of the wait-free structural property, not a circularity: the lemma is not assumed as the conclusion, and the algorithms would be justified if the lemma's proof were repaired. Since the central claims do not reduce to their own inputs by construction, the circularity score is 0.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

No free parameters or invented entities appear. The central algorithms rest on structural optimality lemmas that are asserted and proved in the text, but Lemma 3's proof is not correct as written, so that structural claim is treated as an unverified assumption. Hardness results inherit from cited literature.

assumptions (3)

ad hoc to paper There exists an optimal CLTSP/CLTRP solution that is order-preserving, wait-free for the server, and colliding for clients (Lemmas 1, 2, 3, 4, 11, 12, 13).
Foundational for Algorithms 1-3. The paper attempts proofs, but Lemma 3's position update is inconsistent with its own inequalities, and Lemma 8's strict inequality is actually an equality after substitution.
domain assumption Known complexity results for LTSP/LTRP without collaboration (Tsitsiklis 1992; Sitters 2004; Afrati et al. 1986; Bock 2015; Bock and Klamroth 2013; Garcia et al. 2002).
Used to derive Corollaries 15 and 16 and to transfer hardness to slow-client versions. These results are not re-derived in this paper.
standard math 3-Partition is strongly NP-complete (Garey and Johnson 1979).
Used in the reduction for Theorem 17.

how reviews work

0 comments

Cite this review

Pith. "Pith review of The Line Traveling Salesman and Repairman Problem with Collaboration." pith.science (2026). https://pith.science/paper/VFYPZ3Q4

@misc{pith2026250604127,
  author       = {Pith},
  title        = {Pith review of: The Line Traveling Salesman and Repairman Problem with Collaboration},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VFYPZ3Q4}},
  note         = {Machine review of arXiv:2506.04127}
}

read the original abstract

In this work, we consider extensions of both the Line Traveling Salesman and Line Traveling Repairman Problem, in which a single server must service a set of clients located along a line segment under the assumption that not only the server, but also the clients can move along the line and seek to collaborate with the server to speed up service times. We analyze the structure of different problem versions and identify hard and easy subproblems by building up on prior results from the literature. Specifically, we investigate problem versions with zero or general processing times, clients that are either slower or faster than the server, as well as different time window restrictions. Collectively, these results map out the complexity landscape of the Line Traveling Salesman and Repairman Problem with collaboration.

Figures

Figures reproduced from arXiv: 2506.04127 by the authors.

**Figure 2.** Illustration of the argument corresponding to Theorem [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗

**Figure 3.** Illustration of the arguments corresponding to Theorem [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

[1]

Afrati, S

F. Afrati, S. Cosmadakis, C. H. Papadimitriou, G. Papageorgiou, and N. Papakostantinou. The com- plexity of the Travelling Repairman Problem.RAIRO-Theoretical Informatics and Applications, 20(1): 79–87, 1986

work page 1986
[2]

S. Bock. Solving the Traveling Repairman Problem on a line with general processing times and deadlines. European Journal of Operational Research, 244(3):690–703, 2015

work page 2015
[3]

Bock and K

S. Bock and K. Klamroth. Minimizing sequence-dependent setup costs in feeding batch processes under due date restrictions.Journal of Scheduling, 16:479–494, 2013

work page 2013
[4]

Gambella, J

C. Gambella, J. Naoum-Sawaya, and B. Ghaddar. The Vehicle Routing Problem with floating targets: Formulation and solution approaches.INFORMS Journal on Computing, 30(3):554–569, 2018

work page 2018
[5]

Garcia, P

A. Garcia, P. Jodr´ a, and J. Tejel. A note on the Traveling Repairman Problem.Networks, 40(1):27–31, 2002

work page 2002
[6]

M. R. Garey and D. S. Johnson.Computers and Intractability; A Guide to the Theory of NP- Completeness.Freeman, San Francisco, 1797

work page
[7]

C. S. Helvig, G. Robins, and A. Zelikovsky. The moving-target Traveling Salesman Problem.Journal of Algorithms, 49(1):153–174, 2003

work page 2003
[8]

J. K. Lenstra, A. R. Kan, and P. Brucker. Complexity of machine scheduling problems.Annals of Discrete Mathematics, 1:343–362, 1977

work page 1977

Show all 16 references

[9]

C. C. Murray and A. G. Chu. The flying sidekick traveling salesman problem: Optimization of drone- assisted parcel delivery.Transportation Research Part C: Emerging Technologies, 54:86–109, 2015

2015
[10]

H. N. Psaraftis, M. M. Solomon, T. L. Magnanti, and T.-U. Kim. Routing and scheduling on a shoreline with release times.Management Science, 36(2):212–223, 1990

1990
[11]

R. A. Sitters.Complexity and Approximation in Routing and Scheduling. Phd thesis, Eindhoven Uni- versity of Technology, Department of Mathematics and Computer Science, 2004

2004
[12]

Stieber and A

A. Stieber and A. F¨ ugenschuh. Dealing with time in the multiple Traveling Salespersons Problem with moving targets.Central European Journal of Operations Research, 30(3):991–1017, 2022

2022
[13]

Stieber, A

A. Stieber, A. F¨ ugenschuh, M. Epp, M. Knapp, and H. Rothe. The Multiple Traveling Salesmen Problem with moving targets.Optimization Letters, 9(8):1569–1583, 2015

2015
[14]

J. N. Tsitsiklis. Special cases of Traveling Salesman and Repairman Problems with time windows. Networks, 22(3):263–282, 1992

1992
[15]

B. Yang, W. Li, J. Wang, J. Yang, T. Wang, and X. Liu. A novel path planning algorithm for warehouse robots based on a two-dimensional grid model.IEEE Access, 8:80347–80357, 2020

2020
[16]

Zhang, A

W. Zhang, A. Jacquillat, K. Wang, and S. Wang. Routing optimization with vehicle–customer coordi- nation.Management Science, 69(11):6876–6897, 2023. Statements and Declarations Competing Interests:The authors declare that they have no competing interests. 19

2023

Pith tools

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

[1] [1]

Afrati, S

F. Afrati, S. Cosmadakis, C. H. Papadimitriou, G. Papageorgiou, and N. Papakostantinou. The com- plexity of the Travelling Repairman Problem.RAIRO-Theoretical Informatics and Applications, 20(1): 79–87, 1986

work page 1986

[2] [2]

S. Bock. Solving the Traveling Repairman Problem on a line with general processing times and deadlines. European Journal of Operational Research, 244(3):690–703, 2015

work page 2015

[3] [3]

Bock and K

S. Bock and K. Klamroth. Minimizing sequence-dependent setup costs in feeding batch processes under due date restrictions.Journal of Scheduling, 16:479–494, 2013

work page 2013

[4] [4]

Gambella, J

C. Gambella, J. Naoum-Sawaya, and B. Ghaddar. The Vehicle Routing Problem with floating targets: Formulation and solution approaches.INFORMS Journal on Computing, 30(3):554–569, 2018

work page 2018

[5] [5]

Garcia, P

A. Garcia, P. Jodr´ a, and J. Tejel. A note on the Traveling Repairman Problem.Networks, 40(1):27–31, 2002

work page 2002

[6] [6]

M. R. Garey and D. S. Johnson.Computers and Intractability; A Guide to the Theory of NP- Completeness.Freeman, San Francisco, 1797

work page

[7] [7]

C. S. Helvig, G. Robins, and A. Zelikovsky. The moving-target Traveling Salesman Problem.Journal of Algorithms, 49(1):153–174, 2003

work page 2003

[8] [8]

J. K. Lenstra, A. R. Kan, and P. Brucker. Complexity of machine scheduling problems.Annals of Discrete Mathematics, 1:343–362, 1977

work page 1977