{"id":"b56a2d0c-b2d2-49f5-8029-6423e62debb1","arxiv_id":"2505.14968","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Planning a drone patrol to minimize worst-case data age is NP-complete, and two Christofides-based algorithms achieve a 1.5 approximation for this objective.","lead":"This paper studies the route a drone should patrol so the oldest data it collects stays fresh. It proves the problem is NP-complete and gives two algorithms that come within 1.5 times the best possible data age.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 1.5-approximation guarantee rests on the instantaneous-offload assumption; if upload time scales with accumulated data, the MAI objective and Lemma 1 break.","rationale":"The reader's weakest assumption is exactly the instantaneous-offload assumption, and I agree that this is the load-bearing boundary of the central claim. The internal derivation of the 1.5-approximation bound is sound under the stated metric complete graph model: the lower bound OPT_MAI ≥ W_TSP + W_MST is valid, the Christofides-based route satisfies MAI ≤ 2(W_MST + 0.5W_TSP), and the ratio calculation is correct. The tightness example in Section IV-B contains notational inconsistencies (e.g., W_MST = N−1 instead of N), but the asymptotic limit can be checked and does not affect the upper-bound guarantee. The evaluation would benefit from code, seeds, and error bars, but that is a reproducibility condition rather than a threat to the theorem. Because the central theoretical claim is sound under its explicit assumptions, the appropriate verdict remains CONDITIONAL: accept the theory conditional on the stated model, and require evaluation artifacts before treating the practical near-optimality claim as fully validated.","tokens_in":13612,"tokens_out":18946,"duration_ms":161831,"concrete_test":"Extend the model with a finite data rate B and per-node generation rate r, so the upload time at a visit to node i is r·(time since last visit)/B. For small random instances (N=8), compute exact optimal MAI under this extended objective via DP and compare SRTT/Enforced MAI. If any instance has ratio >1.5, or if the max-MAI node is not the first visited node, the concern lands; if ratios stay ≤1.5 for a range of r/B up to realistic values, the guarantee is robust.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section III-A assumes data exchange time is negligible, so Eq. (1) makes travel time the only route cost and Eq. (4) gives MAI_R(i) = T_R + T_R(i,0). This assumption is load-bearing: if uploading at a node takes time proportional to the data accumulated since the last visit, then the service time at node i depends on the time between visits, which is route-dependent. For a constant generation rate r and upload rate B, the upload time at a visit is r·(time since last visit)/B ≈ r·T_R/B, so the route cost and the data volume become coupled. The AoI expression becomes T_R + T_R(i,0) + upload_time(i), and the maximum over i is no longer guaranteed to occur at the first visited node because upload_time(i) can differ across nodes (e.g., if generation rates differ or if the drone can partially offload while moving). Consequently, Lemma 1, and the lower-bound argument in Theorem 4 that OPT_MAI ≥ W_TSP + W_MST, rely on the travel-time-only objective. Theorems 4 and 6 therefore certify a 1.5 factor only for the instantaneous-offload model. The paper states this assumption, but the abstract's unqualified 'near-optimal routes' and the drone-application framing make this the main boundary of the central claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies route planning for a patrolling data-collection drone that recurrently visits IoT devices and delivers their data to a server, with the objective of minimizing the maximum age-of-information (MAI). The system is modeled as a complete metric graph, routes are Hamiltonian circuits through the server and all data nodes, and the paper derives that the MAI of a route is the round-trip time plus the return travel time from the first visited data node. It proves that the decision version of the problem is NP-complete by a reduction from Hamiltonian Path, and it proposes two approximation algorithms, SRTT and Enforced, each with a claimed 1.5 approximation ratio for MAI. The paper also reports simulation results on synthetic 8-node and 20-node scenarios, comparing the proposed methods against dynamic programming and the LKH TSP solver.","tokens_in":13885,"tokens_out":27252,"duration_ms":246907,"significance":"If the claims hold, the paper provides a clean complexity classification and constant-factor approximation algorithms for an AoI-aware patrol-routing problem, a useful contribution for applications where data freshness, rather than throughput, is the primary concern. The theoretical development is mostly self-contained and relies on standard ingredients: the Hamiltonian Path reduction, Christofides' TSP algorithm, the Held-Karp dynamic program, and standard metric-graph arguments. The empirical study is also meaningful because it compares against an exact DP baseline and the state-of-the-art LKH solver. The central 1.5 approximation bound is simple and appears sound, although the scope of the model and one tightness proof need clarification before the paper is fully convincing.","major_comments":[{"comment":"The derivation of MAI_R(i) = T_R + T_R(i,0) and the proof of Lemma 1 depend on the assumption that the drone can offload all accumulated data instantaneously, so that travel times are the only route cost. If the offload time at a node is non-negligible and node-dependent, for example proportional to the data accumulated since the previous visit with different generation rates, then the service time at a node becomes route-dependent, the MAI expression gains a node-dependent upload term, and Lemma 1 need not hold. Consequently, the lower bound OPT_MAI >= W_TSP + W_MST used in Theorem 4 is not justified in that more general model. The assumption is stated in Section III-A, but the abstract and conclusion present the 1.5 guarantees without this qualification. I recommend that the authors state explicitly in the theorem statements, abstract, and conclusion that the guarantees are for the instantaneous-offload model, and add a short discussion of what changes when upload times are not negligible.","section":"Section III-A, Eqs. (1)-(4), and Lemma 1"},{"comment":"The tightness argument has a logical slip in the direction of the inequality. To prove a lower bound of 1.5 on the approximation ratio, the MAI of the SRTT route on the constructed instance must be lower-bounded, but the text says 'the MAI of this route is at most (N-2)(1+epsilon)+2N-1' and then treats this quantity as the numerator of a ratio that is 'at least' the displayed limit. An upper bound in the numerator can only give an upper bound on the ratio, so the proof of tightness is invalid as written. In addition, the example defines N as the number of data nodes, while W_MST is reported as N-1; if W_MST is taken over the graph that includes the server, the MST has N edges, not N-1. The asymptotic 1.5 limit may be recoverable, but the argument needs to be rewritten with correct lower bounds and consistent node counts.","section":"Section IV-B, tightness example"}],"minor_comments":[{"comment":"The notation T_R(i,j) is defined in Eq. (1) only for i < j along the route, but the paper frequently uses T_R(i,0) for i > 0. Please define T_R(i,0) explicitly as the travel time from node v_{R,i} to the server v0 along the remainder of the route.","section":"Section III-A, Eq. (1)"},{"comment":"The abbreviation for the Lin-Kernighan-Helsgaun solver is written inconsistently as both LKH and LHK; please standardize to LKH.","section":"Section V-A and throughout"},{"comment":"The proof states that 'when Enforced enforces the shortest edge connected to the server node, it constructs the same spanning tree as SRTT.' If there are multiple shortest edges, this is only true for the particular edge selected by SRTT's Prim construction; since Enforced iterates over all server edges, the argument can be repaired, but the wording should be made precise.","section":"Section IV-C, Theorem 6 proof"},{"comment":"The example uses the condition t_{0,3} > t_{1,3} and then claims t_{0,3} < 101 by the triangle inequality. This is correct, but the caption does not show the value of t_{0,3}; please add the relevant edge weights to the figure or caption so the example is self-contained.","section":"Section IV-C, Figure 3"}],"recommendation":"major_revision","confidential_remarks":"This is a borderline case between minor and major revision. The central 1.5 approximation proofs appear sound, and the NP-completeness reduction is clean. The main issues are the unqualified scope of the instantaneous-offload assumption and an incorrect inequality direction in the tightness proof, both of which are fixable within the manuscript's scope. I would be willing to reconsider a revised version."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the paper delivers: NP-completeness for the MAI-minimizing patrol route and two 1.5-approximation algorithms, all within the stated travel-time-only model. Second, that model boundary is real—the paper states it in Section III-A, but the abstract's unqualified 'near-optimal' invites over-reading.\n\nThe central idea is clean. Lemma 1 shows the worst-case AoI is always at the first visited node, so MAI = 2·T_R − t_{0,first}. That turns the problem into 'find a TSP tour and orient it to maximize the longer server edge.' It's a nice twist on TSP, and the paper correctly demonstrates that minimizing round trip time alone is not the same as minimizing MAI (Figure 3). The NP-hardness reduction from Hamiltonian Path is standard but sound. The lower bound OPT_MAI ≥ W_TSP + W_MST and the 1.5-ratio proof are coherent; the Enforced variant, which tries each edge out of the server and takes the best, is a sensible exploitation of Lemma 1.\n\nSoft spots, in proportion. The tightness example for SRTT (Section IV-B, Figure 2) contains off-by-one errors: with N data nodes plus the server, the MST has N edges of weight 1, so W_MST = N, not N−1 as written. The matching weight and the limiting ratio inherit the same issue. The upper bound still stands, but the claim that 1.5 is tight is not established as written. The evaluation section gives no code, seeds, or variance—just average normalized MAI over 100 synthetic instances. That's tolerable for a theory paper, but it doesn't substantiate 'near-optimal' in a strong sense.\n\nThe stress-test concern about upload time is valid as a boundary condition, not a flaw in the proofs. If upload time scales with accumulated data, MAI becomes coupled with the route, and Lemma 1 plus the 1.5 guarantees would need rework. The paper does disclose the assumption; a follow-up with positive service times would be the natural next step.\n\nWho this is for: people working on UAV patrolling with AoI constraints, and anyone studying how TSP-style objectives diverge from latency-oriented ones. The paper deserves a serious referee. I would send it to review with a request to fix the tightness calculation and to make the evaluation reproducible by releasing code and seeds.","headline":"Clean MAI-patrol theory with a model boundary; tightness and evaluation need polish.","tokens_in":14399,"tokens_out":6751,"would_cite":true,"duration_ms":55951,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68W25","90C27"],"pacs":[],"model":"deepseek-v4-flash","headline":"Planning a drone patrol route that minimizes the worst-case age of collected data is NP-complete, but two polynomial-time algorithms guarantee routes within 1.5 times the optimal maximum age.","keywords":["maximum age-of-information","patrolling drone","piggyback network","store-carry-forward","approximation algorithm","NP-complete","traveling salesman problem","route planning"],"falsifier":"Run the exact dynamic programming algorithm for optimal MAI on a small metric complete graph, generate the SRTT and Enforced routes, and compare the ratios; the theorems assert the ratio never exceeds 1.5, so any instance with a ratio above 1.5 would refute the approximation claim. A complementary check is to set up a simulation where data upload time is nonzero and grows with accumulated data; the predicted MAI formula would then systematically underestimate the measured maximum age.","tokens_in":13435,"feed_emoji":"🚁","tokens_out":9143,"duration_ms":73648,"temperature":0.7,"pith_summary":"This paper studies a patrol drone that visits stationary IoT devices, collects data packets they generate recurrently, and delivers them to a server. The goal is to choose a cyclic patrol route that minimizes the Maximum Age-of-Information (MAI), the oldest data that can arrive at the server. The paper proves that deciding whether a route exists with MAI at most a given threshold is NP-complete, and then offers two approximation algorithms, SRTT and Enforced, each proven to return a route whose MAI is at most 1.5 times the optimal MAI on metric complete graphs. The key structural insight is that the worst-case age of any route is always set by the first device visited, which reduces the problem to a structured variant of the traveling salesman problem.","feed_headline":"Patrolling drone routes get a 1.5x data-freshness guarantee","feed_subtitle":"Two route planners provably hold worst-case data age to 1.5x the optimum.","key_machinery":"The load-bearing object is the first-node lemma: for a route $R$, $\\mathrm{MAI}_R = T_R + T_R(1,0)$, so the maximum age is always at the first visited data node. Writing this as $2T_R - T_R(0,1)$ reveals the counterintuitive mechanism--extending the first leg out of the server can reduce the MAI even when it increases total route length. The approximation proofs then use the triangle inequality together with the standard 1.5-approximation for the traveling salesman problem, constructed from a minimum spanning tree plus a minimum-weight perfect matching, to bound the round trip time of the produced route against the optimal TSP tour, which in turn bounds the MAI.","core_discovery":"The paper's central claim is that, for a patrolling drone collecting recurrently generated data, the Maximum Age-of-Information of a route obeys a simple identity: $\\mathrm{MAI}_R = T_R + T_R(1,0)$, where $T_R$ is the round trip time and $T_R(1,0)$ is the travel time from the first data node visited back to the server. Because the return time from the first node is the largest among all nodes, this identity localizes the worst-case age to the first leg of the route. From it the paper derives that the decision version of the route-planning problem is NP-complete by a reduction from Hamiltonian Path, and that two polynomial-time heuristics--Shortest Round Trip Time, built on the standard 1.5-approximation algorithm for the traveling salesman problem, and Edge Enforcement, which tries every possible first edge--both guarantee an MAI within a factor of 1.5 of the optimum. The paper further shows empirically that the shortest round trip time route is not necessarily the freshest route, and that combining Enforced with a state-of-the-art TSP solver produces near-optimal MAI in most test scenarios.","pith_inferences":["The asymmetry of the MAI objective under route reversal is reminiscent of minimum-latency problems, and the first-node decomposition may extend to other freshness metrics such as average age or peak age under different arrival processes.","If per-visit data transfer time grows with the volume accumulated, the model becomes a joint routing and scheduling problem; the identity here suggests that the first-leg tradeoff would persist but the 1.5 approximation would need re-derivation.","Because the tightness ratio for Enforced is only shown to be at least 1.375, a refined analysis could possibly improve the approximation guarantee within the same algorithmic framework."],"forward_implications":["The first-node lemma reduces MAI route planning to choosing a first device and then finding the shortest Hamiltonian path back to the server, so exact optimization is possible only for small instances.","A shorter round trip time can increase the worst-case data age, so freshness-aware routes must be planned with a different objective than classic TSP.","Both proposed algorithms run in polynomial time and carry a certified worst-case guarantee of 1.5, making them deployable for route updates when nodes are relocated.","The hybrid of Enforced and a TSP solver reached the optimal MAI in at least 66% of the 8-node and 30% of the 20-node test scenarios, indicating near-optimal practical performance."],"supporting_citations":[{"why":"Provides the 1.5-approximate TSP construction that both SRTT and Enforced use to bound route length.","marker":"[13]"},{"why":"Supplies the dynamic programming method that computes exact optimal MAI routes for small instances and defines the exponential baseline.","marker":"[12]"},{"why":"Establishes the NP-completeness of Hamiltonian Path, the source problem in the hardness reduction.","marker":"[16]"},{"why":"Documents very high wireless data rates that justify the assumption of negligible data exchange time at a node.","marker":"[15]"},{"why":"Supplies the state-of-the-art TSP solver used as the empirical baseline and in the hybrid approach.","marker":"[20]"}],"fun_headline_variants":["Drone patrol routes: 1.5x data-age guarantee","Patrolling drones: worst-case data age held to 1.5x","NP-complete AoI routing has 1.5x approximation","Max-age identity yields 1.5x freshness for drone fleets","1.5x optimal data age achievable for drone patrols"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The model assumes the drone can offload all accumulated data at a node instantly, so the age of delivered data depends only on travel times and not on the volume of data being transferred.","fun_headline_variants_meta":{"raw":{"variants":["Drone patrol routes: 1.5x data-age guarantee","Patrolling drones: worst-case data age held to 1.5x","NP-complete AoI routing has 1.5x approximation","Max-age identity yields 1.5x freshness for drone fleets","1.5x optimal data age achievable for drone patrols"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000428,"raw_usage":{"total_tokens":2221,"prompt_tokens":1011,"completion_tokens":1210,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":627,"completion_tokens_details":{"reasoning_tokens":1117}},"tokens_in":627,"tokens_out":1210,"duration_ms":10627,"temperature":1.0,"reasoning_tokens":1117,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T15:27:07.586931+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the exact dynamic programming algorithm for optimal MAI on a small metric complete graph, generate the SRTT and Enforced routes, and compare the ratios; the theorems assert the ratio never exceeds 1.5, so any instance with a ratio above 1.5 would refute the approximation claim. A complementary check is to set up a simulation where data upload time is nonzero and grows with accumulated data; the predicted MAI formula would then systematically underestimate the measured maximum age.","supporting_citations":[{"cited_title":"Worst-case analysis of a new heuristic for the travelling salesman problem,","cited_arxiv_id":null,"evidence_quote":"Provides the 1.5-approximate TSP construction that both SRTT and Enforced use to bound route length."},{"cited_title":"Dynamic programming treatment of the travelling sales- man problem,","cited_arxiv_id":null,"evidence_quote":"Supplies the dynamic programming method that computes exact optimal MAI routes for small instances and defines the exponential baseline."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the NP-completeness of Hamiltonian Path, the source problem in the hardness reduction."},{"cited_title":"Ieee 802.11ay: Next-generation 60 ghz communication for 100 gb/s wi-fi,","cited_arxiv_id":null,"evidence_quote":"Documents very high wireless data rates that justify the assumption of negligible data exchange time at a node."},{"cited_title":"An extension of the lin-kernighan-helsgaun tsp solver for constrained traveling salesman and vehicle routing problems,","cited_arxiv_id":null,"evidence_quote":"Supplies the state-of-the-art TSP solver used as the empirical baseline and in the hybrid approach."}],"review_version":1}