- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies incremental metric routing, where each arriving transportation request must be inserted without changing the relative order of earlier requests. Before arrivals begin, the algorithm receives one independent sample from each request distribution. A sample-based backbone and local excursions yield a expected competitive ratio for one vehicle and a guarantee for multiple vehicles. A separate budget-doubling algorithm is analyzed for adversarial sample corruption, with logarithmic dependence on the number of corrupted samples. Experiments use a fixed adversarial request sequence and synthetically generated predictions.
Critical strengths
The reliable-sample result is a meaningful theoretical contribution. One independent sample per request distribution suffices for a constant expected guarantee in arbitrary symmetric metrics, without requiring identical distributions or distributional regularity. The backbone-plus-excursion analysis, particularly the exchange argument excluding a request's own sample, explains why this limited information is useful. The multi-vehicle extension broadens the result beyond a single route.
Critical weaknesses
-
The robustness extension does not establish the main quantitative guarantee for a single robust algorithm, and its implementation and analysis contain unresolved gaps.
The guarantee applies to Algorithm 1, whereas the corruption-dependent guarantee applies to Algorithm 2. The paper does not establish that one algorithm retains the guarantee when while degrading logarithmically with corruption. An asymptotic constant at is not the same quantitative guarantee. Although this is not a contradiction between the individual theorem statements, it materially limits the interpretation that the main result has been preserved under a robust extension. The no-corruption constant of Algorithm 2 should be stated explicitly.
Moreover, Algorithm 2, lines 7–10, observes an initial prefix through index , sets , and initializes , without inserting that prefix into the output. For two TSP requests at distinct locations, the first positive-cost prefix contains both requests; the loop is then skipped and the pseudocode returns an empty graph. The prose suggests that the prefix is processed, but neither its route nor its cost is incorporated explicitly. Lemma 7 also assumes a preceding budget-doubling phase and does not address termination at the initial budget. A corrected algorithm and complete accounting of the initialization are necessary to substantiate the robust guarantee.
-
The experimental sampling protocol does not match the independence assumption underlying the main theorem.
Section 2 assumes independent draws . In Section 5, the actual requests are fixed, while each sample is generated around the corresponding realized request: it remains at that location with probability and otherwise moves according to an inverse-distance distribution. This is a different prediction model. Repeating sample generation around one fixed sequence does not evaluate the expectation over independent actual requests and samples required by the theorem.
The experiments may demonstrate usefulness under spatially correlated forecasts, but they do not validate the stated single-sample guarantee. Consequently, the claim that Figure 2 confirms the theoretical constant-factor guarantee is unsupported by this protocol. Additionally, the offline reference is a -approximation, so proximity to this reference does not establish proximity to the true offline optimum.
Questions for authors
-
Please state the guarantees of each algorithm separately, including the no-corruption constant of Algorithm 2. Does any algorithm simultaneously achieve the reliable-sample guarantee and the corruption-dependent bound? Please also provide a corrected initialization and an analysis accounting for the initial prefix and initial budget.
-
How can the experimental protocol be reconciled with the assumption that actual requests and samples are independent draws from the same distributions? Is there validation under the stated model? Otherwise, which empirical conclusions remain justified, particularly the claimed confirmation of the theoretical guarantee?
2 comments
Follow Up
Dear Reviewer,
Thank you again for your review and feedback. As the discussion period continues, we would like to follow up to ensure that our rebuttal adequately addressed the technical concerns you raised.
Please do not hesitate to let us know if any further clarifications would be helpful. We greatly appreciate your time and dedication to reviewing our work.
Thank you for your review. Below we provide responses to your questions and concerns.
No, Algorithm 1 achieves an expected competitive ratio of 3.5 when all samples are reliable, whereas Algorithm 2 achieves O(log(pn)) (i.e., O(logk)) under k corrupted samples and an explicit constant of 41 when k=0. Trading off a looser consistency constant to gain worst-case robustness against unknown adversarial errors is standard in learning-augmented algorithms (e.g., Lykouris & Vassilvitskii, 2018; Purohit et al., 2018; Mitzenmacher & Vassilvitskii, 2020). Because Algorithm 2 does not know k in advance, it replaces Algorithm 1's single 1.5-approximate TSP tour with an online budget-doubling search using 2-approximate rooted k-TSP backbones. Moreover, in Section 4 we prioritized proof simplicity rather than optimizing the leading constant at k=0 (which can be tightened—for example, by tuning the phase-scaling multiplier and phase threshold—without changing the algorithmic framework). When samples are known to be reliable, the simpler Algorithm 1 is specifically designed for that regime. At the same time, as shown in Figure 2a (p=0.0), in practice Algorithm 2's tour cost without corruption is nearly indistinguishable from Algorithm 1's, indicating that the analytical constant from worst-case doubling is conservative. For this reason, although we provide the explicit bound of 41 here in response to the reviewer’s question, we have not included this numerical constant in the paper. The goal of our robustness result is to establish that a single algorithm retains a constant competitive ratio with reliable samples while degrading only logarithmically with corruption; optimizing the particular constant in the no-corruption case is outside the scope of this work, and the bound of 41 is not intended to be tight.
We thank the reviewer for catching that we set M←∅ instead of initializing M with the prefix tour in Algorithm 2. We have updated Lines 7–10 so that M is initialized with the tour serving R1,…,Rℓ in arrival order until c(M)>0 (or ℓ=n), with i←ℓ+1 and T←c(M). This directly resolves the boundary cases as well: whenever ℓ=n (such as two TSP requests at distinct locations, or when all requests have zero cost), i=n+1 skips the
whileloop and returns M covering all n requests. Finally, because the tour on R1,…,Rℓ−1 has zero cost, all vertices in V(R<ℓ) have distance zero to s1, so this initial tour has cost T0≤c(OPT(R)) by the triangle inequality. Carrying T0 through Lemma 7 (Tfinal≤T0+2T∗+Wmax, which also covers termination at the initial budget without a preceding doubling phase) and Lemma 8 (ALG≤T0+8Tfinal≤9T0+16T∗+8Wmax) adds at most 9E[c(OPT(R))] and leaves our O(log(pn)) guarantee unchanged.Thank you for this careful reading. You are right on both points, and we have redone the experiments accordingly.