{"id":"d689624e-5563-47f2-bc10-1eefb64bfd28","arxiv_id":"2411.17271","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"An O(n log n log log n)-time algorithm finds the minmax-regret broadcast center in a tree when every edge weight can vary within an interval under the postal model.","lead":"This paper designs a fast algorithm for finding the best place to start a broadcast in a tree-shaped network when link speeds are only known as ranges. If correct, it is the first such algorithm that handles uncertainty in link weights under the postal communication model.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the flagged α_{x,y} inconsistency is a notational/typo issue, not a mathematical one; the scenario-reduction proofs check out on close reading.","rationale":"The reader's conditional verdict identifies the scenario-reduction step as the weakest assumption, and I agree that this is the most complex and load-bearing part of the paper. However, on close inspection the specific flagged inconsistency between the definition of α_{x,y} and Facts 1–2 does not land: those facts intentionally restrict α's assignment to P_{x,y} ∪ E(B_{y,x}), which is a coherent subset of α's specification. The proof of Fact 2's iterative step is terse, but the set-inclusion and weight-consistency arguments check out. I also verified the key algebraic steps of Fact 3 and Lemma 13, including the use of Lemma 5 and Lemma 4, and found no concrete gap. The complexity proof in Section 5 is dense and unverified by machine-checking, so I cannot rule out a subtle data-structure error, but I found no specific flaw to report. Given this, the appropriate verdict remains CONDITIONAL: the paper should be accepted only after the authors clarify the α notation, fix the typo in Fact 3's proof, and ideally provide a small worked example or executable verification of the candidate-set search. My read does not change the reader's verdict, hence UNCHANGED.","tokens_in":38336,"tokens_out":37059,"duration_ms":306646,"concrete_test":"Implement a brute-force verifier for n ≤ 8: for random trees and interval weights, enumerate all scenarios that assign each edge an endpoint or a fine-grid interior value, compute the true maximum regret of each vertex, and compare against the candidate-set maximum used by Algorithm 2 (the β^j scenarios of Lemma 13). Repeat on 1000 random instances; any mismatch would pinpoint the failing fact, while a clean run would corroborate the scenario reduction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I re-examined the reader's primary concern: the definition of α_{x,y} in Section 3 (high on P_{x,y} ∪ E(\\bar{B}_{y,x}), low on E(B_{y,x})) versus its use in Facts 1–2 (specifying P_{x,y} ∪ E(B_{y,x})). These are not contradictory. Facts 1 and 2 only borrow α's weights on a subset: along the path P_{x,y} they are high, and on the x-side component E(B_{y,x}) they are low; the y-side component E(\\bar{B}_{y,x}) is left to the previous worst-case scenario. The equality w^{s1} = α_{x,y1} = α_{x,κ1} on P_{x,κ1} ∪ E(B_{κ1,x}) in the proof of Fact 2 holds because both base scenarios set the path high and the x-side branches low. The apparent 'b_time^α(x, \\bar{B}_{y,x})' in the proof of Fact 3 is a typo: the required inequality is b_time^α(y, \\bar{B}_{y,x}) ≥ b_time^{¨s}(y, \\bar{B}_{y,x}), which follows since α sets all weights in \\bar{B}_{y,x} to their upper endpoints. I found no invalid step in Facts 1–4, Lemma 7, Lemma 13, or the complexity analysis in Section 5. The remaining risk is the usual one for a long, unformalized proof: a subtle indexing or ordering error in the succ(j) construction could affect the O(n log log n) bound, but I could not locate a concrete failure.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper considers the broadcast-center problem on a tree under the postal model when every edge weight is an interval of possible values, and adopts the minmax-regret criterion. The central claim is Theorem 9: a minmax-regret broadcast center of an n-vertex tree with interval edge weights can be computed in O(n log n log log n) time. The proposed method is a prune-and-search procedure (Algorithm 1) that repeatedly chooses a centroid x of the current search region, computes a worst-case scenario for x, and applies Lemma 7 to restrict the search. The main technical contribution is the reduction of the infinite scenario space for each vertex x to at most n-1 candidate scenarios, constructed from base scenarios α_{x,v_i} and modified scenarios β^j_{x,v_i}. Correctness is developed through Facts 1-4 and Lemmas 10-13, and the O(n log log n) worst-case-scenario search is based on bucket structures, predecessor/successor lists, and van Emde Boas priority queues.","tokens_in":38632,"tokens_out":30317,"duration_ms":285470,"significance":"If the claimed result is correct, it is a substantial algorithmic contribution: it extends deterministic postal-model broadcasting [33] to robust optimization under interval edge weights, and it does so with the same type of bound as the robust 1-center problem of Burkard and Dollani up to an O(log log n) factor. The paper contains a fully specified algorithm, a parameter-free finite scenario reduction, and a serious attempt at a self-contained correctness proof. The use of a finite candidate set for the worst-case scenario is the key idea and is falsifiable in the sense that the proof gives explicit scenarios that are claimed to attain the maximum regret. The main proof is not machine-checked, and the complexity analysis depends on a long and intricate successor-list construction, so the significance should be read as conditional on the completeness of that analysis.","major_comments":[{"comment":"The proof of the O(n log log n) evaluation of the maximum in Lemma 13 is incomplete. The text states that b_time^{β^j}_{x,v_i}(v_i, \\bar B_{v_i,x}) \"and b_time^{β^j}_{x,v_i}(v_i,T) similarly\" can be determined in O(n log log n) time, but then the detailed bucket/pred/succ construction is given only for b_time^{β^j}_{x,v_i}(v_i, \\bar B_{v_i,x}). The two quantities are not literally the same: broadcasting from v_i to all of T includes the additional neighbor µ in B_{v_i,x}, and the position of µ in the optimal neighbor ordering, as well as the positions of the u_{i,k} with smaller values, depends on β^j. Since Lemma 13's expression subtracts b_time^{β^j}(v_i,T), an incorrect or omitted evaluation would change the scenario selected. Please provide the details of how µ is folded into the bucket/pred/succ structure, or give a separate derivation of the full broadcast time, and confirm that the O(h_i log log h_i) bound is preserved.","section":"Section 5, paragraph after Lemma 13"},{"comment":"The inequality Σ_{1≤j≤h_i} δ_j ≤ 2(h_i-1) is asserted rather than proved. Here δ_j is the number of buckets deleted from succ(j+1) when constructing succ(j). The preceding sentence accounts for buckets newly added to some succ(j) (at most two per step), but it does not rule out the possibility that a bucket index is deleted at one level and reinserted at a later (smaller) level. If reinsertion can occur, Σ δ_j could be larger, and the O(h_i log log h_i) bound for the deletions would fail. Because this bound is load-bearing for the claimed overall complexity, please supply an explicit charging argument showing that each deleted bucket is charged to a distinct creation event, or prove a monotonicity property that prevents reinsertion.","section":"Section 5.1, paragraph 'The overall time complexity...'"}],"minor_comments":[{"comment":"The definition sets w^{α_{x,v_i}}_{a,b}=w^+_{a,b} on P(x,v_i) ∪ E(\\bar B_{v_i,x}), while Facts 1 and 2 refer to weights on P_{x,y} ∪ E(B_{y,x}). These are consistent because B_{y,x} is the x-side component and E(B_{y,x}) is exactly the set on which α takes the lower endpoints, but the paper should state this reconciliation explicitly to avoid the apparent mismatch.","section":"Section 3, definition of α_{x,v_i}"},{"comment":"The pseudocode does not explicitly say that, in every iteration, ¨s(z), BCtr^{¨s(z)}, and B_{z,κ} in line 8 are all evaluated with respect to the original input tree T, not with respect to the current subtree T′. The surrounding text indicates this, but the ambiguity is important because Lemma 7 is a statement about the original T; please add a sentence or a note to the pseudocode.","section":"Algorithm 1, lines 4-9"},{"comment":"There are several typographical errors: 'Th e broadcasting' in the abstract and 'wights' in Table 1 should be corrected. These do not affect the mathematics.","section":"Abstract and Table 1"},{"comment":"The definitions of pred(j) and succ(j) as lists of non-empty buckets are dense and would benefit from a short intuitive explanation: pred(j) records the buckets to the left of τ_j that are possible bottlenecks for the prefix, and succ(j) records the analogous buckets to the right. This would make the four stages of the construction much easier to follow.","section":"Section 5.1, definitions of pred(j) and succ(j)"},{"comment":"The existence and role of Q_{t*} is proved inline after the definition, but a high-level sentence stating that t* is the first moment when the bottleneck of the y-to-\\bar B_{y,x} broadcast is the next vertex to be fixed would improve readability.","section":"Section 4.4, definition of t*"}],"recommendation":"major_revision","confidential_remarks":"The stress-test note and the reader's report agree that the flagged α_{x,y} inconsistency is a notational issue, and I concur after reading the relevant definitions. My recommendation of major revision is driven by two missing details in the complexity proof: the 'similarly' treatment of b_time^{β^j}(v_i,T) and the charging argument for Σδ_j. Both are local in the sense that they can be repaired within the scope of the manuscript, but they are load-bearing for Theorem 9 as stated, so I would not accept the paper in its current form. The paper is otherwise in scope for cs.DS and appears to be a genuine extension of [33] rather than a repackaging of it."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the result is real, and the reader's main worry is a notational slip rather than a flaw. The paper gives the first O(n log n log log n) algorithm for the minmax-regret broadcast center on a tree with interval edge weights under the postal model, extending Burkard and Dollani's robust 1-center result to rho > 0 with only an O(log log n) penalty. That is the correct headline.\n\nWhat it does well: the scenario reduction is the meat. They prove a worst-case scenario for a fixed vertex can be found among at most n-1 candidates (Facts 1-4 and Lemma 13), then show how to evaluate those candidates in O(n log log n) after O(n log n) preprocessing. The prune-and-search wrapper (Lemma 7) is clean. The bucket and van Emde Boas machinery in Section 5 is intricate but the amortization argument is plausible; I did not find a concrete error.\n\nOn the flagged inconsistency: Section 3 defines α_{x,y} with high weights on P_{x,y} ∪ E(\\bar{B}_{y,x}) and low elsewhere, while Fact 1 and 2 use weights on P_{x,y} ∪ E(B_{y,x}). These are not in conflict. Facts 1-2 only use α's weights along the path (high) and on the x-side component (low); the y-side component is left to the previous worst-case scenario. The stress-test note is right that the apparent 'b_time^α(x, \\bar{B}_{y,x})' in the Fact 3 proof is a typo for b_time^α(y, \\bar{B}_{y,x}). That said, the presentation is genuinely confusing here, and the authors should rewrite the definitions to say explicitly which components are fixed at which endpoints in each fact. A referee should ask for that.\n\nThe reliance on Lemmas 4 and 8 from the authors' earlier work [33] is acceptable; those are building-block lemmas about the deterministic postal model, not the target result. The citation pattern is normal.\n\nRemaining risk is the usual one for a long unformalized proof: a subtle ordering error in the succ(j) update could break the O(log log n) per-vertex claim. I could not find one, and the stress-test pass agrees. The paper deserves a serious referee; it is not a desk reject. I would send it out with a request to clarify the scenario definitions and to make the succ(j) invariants easier to verify.","headline":"First minmax-regret broadcast center algorithm for trees with interval weights; the flagged α inconsistency is a typo and the core proofs hold up under close reading.","tokens_in":39217,"tokens_out":3427,"would_cite":true,"duration_ms":27496,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68R10","05C85","68W40"],"pacs":[],"model":"deepseek-v4-flash","headline":"A minmax-regret broadcast center on a tree with interval edge weights can be found in O(n log n log log n) time.","keywords":["broadcasting","minmax-regret","tree network","edge weight uncertainty","postal model","worst-case scenario","prune-and-search","interval weights"],"falsifier":"Take a small tree with interval weights and positive $\\rho$, run Algorithm 2 to obtain every candidate scenario $\\beta^j_{x,y}$, then sample a dense grid of actual scenarios from the interval product $C$ and compute the relative regret $r^s_{x,y}$ for each sample; if any sampled scenario gives a strictly larger regret than every candidate $\\beta$, the scenario reduction is false and the algorithm's output cannot be certified as a worst-case scenario.","tokens_in":38090,"feed_emoji":"📡","tokens_out":8977,"duration_ms":73815,"temperature":0.7,"pith_summary":"This paper claims that the robust broadcasting problem on a tree—where each edge weight is only known to lie in an interval and the goal is to choose one broadcast center that minimizes the worst-case regret—can be solved in $O(n\\log n\\log\\log n)$ time under the postal model. That matters because choosing a message source without knowing actual bandwidths can otherwise be badly suboptimal, and a naive search over all edge-weight scenarios is infinite. The paper shows that for each candidate vertex the infinite scenario space can be collapsed to at most $n-1$ candidate scenarios, and that a centroid-based prune-and-search needs only $O(\\log n)$ rounds. A sympathetic reader would take the contribution as showing that minmax-regret broadcasting on trees with interval weights and a positive per-call setup cost $\\rho$ is solvable in near-linear time rather than requiring exhaustive scenario search.","feed_headline":"Minmax-regret broadcast center on trees: O(n log n log log n)","feed_subtitle":"Edge weights known only as ranges make every source a gamble; this algorithm picks the source with the smallest worst-case regret.","key_machinery":"The load-bearing machinery is the base scenario $\\alpha_{x,y}$ and its derived scenarios $\\beta^j_{x,y}$, indexed by the neighbors $u_{i,1},\\ldots,u_{i,h_i}$ of a candidate vertex $v_i$ outside the branch containing $x$. Facts 1 and 2 assert that a worst-case scenario can be assumed to agree with $\\alpha_{x,y}$ on the $x$-to-$y$ path and on the component $B_{y,x}$, while Facts 3 and 4 fix the remaining branch weights, so the true worst case lies among at most $n-1$ candidates. The broadcast-time decomposition of Lemma 4, $b\\text{times}(x,T)=d_{x,\\kappa}\\rho+\\tilde{w}^s_{x,\\kappa}+b\\text{times}(\\kappa,\\bar{B}_{\\kappa,x})$, turns regret comparisons into path-weight sums plus two subtree broadcast times, and Lemma 13 says the best candidate maximizes exactly that combination. Bucket structures storing $\\text{acc}(\\ell)$ and $\\min v(\\ell)$, together with a van Emde Boas priority queue, maintain the optimal broadcast sequence across all $\\beta^j_{x,y}$ in $O(n\\log\\log n)$ time per source.","core_discovery":"The central claim is that a minmax-regret broadcast center of an $n$-vertex tree with interval edge weights, under the postal model with connection time $\\rho>0$, can be computed in $O(n\\log n\\log\\log n)$ time. For any fixed candidate source $x$, the paper constructs a finite family of scenarios with at most $n-1$ members total, and proves, through a chain of scenario transformations, that some member of this family is a worst-case scenario for $x$. This reduces the infinite maximum-regret computation to evaluating $O(n)$ specially defined scenarios $\\beta^j_{x,v_i}$. The paper then shows that evaluating all of them, after $O(n\\log n)$ preprocessing, takes $O(n\\log\\log n)$ time per vertex, and that the centroid-based search visits $O(\\log n)$ subtrees, yielding the stated bound.","pith_inferences":["The $O(\\log\\log n)$ factor enters through the van Emde Boas priority queue rather than through the combinatorial structure, so in special cases such as $\\rho=0$ a different bucketing scheme might remove that factor entirely.","The scenario-collapse recipe—find a finite extreme-point scenario family for the structural optimum, then prune-and-search over centroids—likely transfers to other communication models on trees, such as the telephone or cable model, where a broadcast center is defined by different recurrence relations.","A direct empirical validation would enumerate all vertices on small random trees, sample the interval scenario space densely, and confirm that the $\\beta$ candidates always attain at least the sampled regrets; a violation would pinpoint exactly which of Facts 1–4 fails."],"forward_implications":["Network operators on tree topologies can choose a broadcast source whose worst-case loss is minimized, even when link delays are known only as ranges, in time nearly linear in the network size.","The infinite scenario space of minmax regret on trees is shown to reduce to a finite candidate set of size at most $n-1$ per source, a structural fact usable in other robust tree-location problems.","Setting the postal-model parameter $\\rho=0$ recovers a robust 1-center problem, so the known $O(n\\log n)$ robust 1-center result becomes the special case of a single algorithm with an extra $O(\\log\\log n)$ factor.","The result marks the tree case of robust broadcasting with interval weights as polynomial, leaving NP-hardness only for general topologies."],"supporting_citations":[{"why":"It supplies the linear-time broadcast-center subroutine, the optimal-sequence lemma used for scheduling, and the broadcast-time decomposition on which the scenario transformations rest.","marker":"[33]"},{"why":"It establishes the earlier $O(n\\log n)$ robust 1-center result on trees, the $\\rho=0$ baseline that the paper extends to the postal model.","marker":"[14]"},{"why":"It provides the van Emde Boas priority queue whose $O(\\log\\log n)$ operations create the per-vertex time bound within the search.","marker":"[34]"},{"why":"It supplies the centroid property and linear-time centroid computation that keep the prune-and-search loop to $O(\\log n)$ iterations.","marker":"[19]"},{"why":"Together with the centroid references, it certifies the $O(n)$ centroid step used at every level of the recursion.","marker":"[23]"},{"why":"It shows the deterministic broadcasting problem is NP-hard on general topologies, motivating the tree restriction that makes the polynomial result meaningful.","marker":"[32]"}],"fun_headline_variants":["Minmax-regret broadcast center: near-linear time on trees","Robust broadcast source selection under edge uncertainty","Fast algorithm for minmax-regret broadcast in trees","Edge-weight uncertainty: minmax-regret broadcast center in trees"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole argument depends on Facts 1 and 2: that every worst-case scenario can be transformed, without reducing the regret, into one whose weights on the path from $x$ to $y$ and on the branch containing $y$ are at the extreme values of the base scenario $\\alpha_{x,y}$; if that collapse misses the true worst case, the candidate set is too small and Algorithm 2 can return a scenario that is not actually worst-case.","fun_headline_variants_meta":{"raw":{"variants":["Minmax-regret broadcast center: near-linear time on trees","Robust broadcast source selection under edge uncertainty","Fast algorithm for minmax-regret broadcast in trees","Edge-weight uncertainty: minmax-regret broadcast center in trees"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001143,"raw_usage":{"total_tokens":4664,"prompt_tokens":784,"completion_tokens":3880,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":400,"completion_tokens_details":{"reasoning_tokens":3815}},"tokens_in":400,"tokens_out":3880,"duration_ms":29021,"temperature":1.0,"reasoning_tokens":3815,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T12:25:52.745523+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small tree with interval weights and positive $\\rho$, run Algorithm 2 to obtain every candidate scenario $\\beta^j_{x,y}$, then sample a dense grid of actual scenarios from the interval product $C$ and compute the relative regret $r^s_{x,y}$ for each sample; if any sampled scenario gives a strictly larger regret than every candidate $\\beta$, the scenario reduction is false and the algorithm's output cannot be certified as a worst-case scenario.","supporting_citations":[{"cited_title":"Su, C.-C","cited_arxiv_id":null,"evidence_quote":"It supplies the linear-time broadcast-center subroutine, the optimal-sequence lemma used for scheduling, and the broadcast-time decomposition on which the scenario transformations rest."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It establishes the earlier $O(n\\log n)$ robust 1-center result on trees, the $\\rho=0$ baseline that the paper extends to the postal model."},{"cited_title":"van Emde Boas, R","cited_arxiv_id":null,"evidence_quote":"It provides the van Emde Boas priority queue whose $O(\\log\\log n)$ operations create the per-vertex time bound within the search."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It supplies the centroid property and linear-time centroid computation that keep the prune-and-search loop to $O(\\log n)$ iterations."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Together with the centroid references, it certifies the $O(n)$ centroid step used at every level of the recursion."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It shows the deterministic broadcasting problem is NP-hard on general topologies, motivating the tree restriction that makes the polynomial result meaningful."}],"review_version":1}