{"id":"4a37638c-5f6e-4e5f-b01b-3b359cf52170","arxiv_id":"2505.03908","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A polynomial-time algorithm for unsplittable flow routing in Clos networks guarantees congestion at most 9/5 of optimal, with lower bounds of 3/2 offline and 2 online.","lead":"This paper proves that data-center networks can route unsplittable data flows with at most 1.8 times the ideal congestion, improving on the previous best factor of 2. It also shows a strict separation: no online algorithm can beat a factor of 2 when flows arrive one at a time.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Q3 gap is real in the written proof: Theorem 4.1 needs a per-link congestion bound, but Lemma 4.2 proves only an aggregate sum. The missing per-link statement is derivable from P1/P2 and L≤max demand, so the issue is repairable rather than fatal.","rationale":"The reader's weakest-assumption analysis locates the same load-bearing point: Theorem 4.1's contradiction requires a per-link congestion lower bound on every non-congested link leaving I_i(f), but the formal statement of Lemma 4.2 Q3 proves only an aggregate sum of per-copy minimum demands. That mismatch is a genuine gap in the written proof, and it is exactly where the argument could fail. I checked whether the gap is fatal. It is not obviously fatal: the missing per-link inequality can be derived from P1, P2, the rejection condition, and the definition of L, because full lower copies occupy every middle switch in the link-disjoint Phase 1 routing, and P2 lets each per-copy minimum be bounded below by the next copy's maximum. Thus the theorem is likely repairable, but the repair is not present in the manuscript. The online lower bounds and offline NP-hardness sections appear independent of this issue and are convincing. Since the main offline theorem's written proof has a real, though patchable, gap, the conditional verdict is appropriate; I would not move it to ACCEPT without the per-link argument being written out.","tokens_in":22407,"tokens_out":19844,"duration_ms":193856,"concrete_test":"Independently re-derive the per-link Q3 bound: for a flow f rejected by I_i with x≥3, prove that for every middle switch m, congestion(I_iM_m) ≥ Σ_{k=1}^{x−1} +d^k_i ≥ (Σ_{k=1}^{x−1}+D^k_i + max{+D^x_i, dem(f)}) − +D^1_i > pL − L = (p−1)L, using P1 (lower copies full), P2 (demands non-increasing across copies), the rejection inequality, and L ≥ max demand at I_i. If this derivation is valid, the Theorem 4.1 gap is closable; if it fails on some instance satisfying P1–P3, the central proof remains invalid.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 4.1 derives the contradiction\nΣ_{h∈H:i(h)=i(f)} dem(h) > C·D + (N−C)(p−1)L.\nThe term (N−C)(p−1)L is justified only if every non-congested link leaving I_i(f) has congestion > (p−1)L. Lemma 4.2, however, proves in Q3 only the aggregate bound Σ_k +d^k_i > (p−1)L; that aggregate bound alone does not control individual links. As written, the step is therefore a gap. The gap is patchable: if I_i rejected f at copy x, then copies 1,…,x−1 are full, and in the link-disjoint Phase 1 routing each full copy contributes exactly one flow to every middle switch, so every link I_iM_m carries at least Σ_{k=1}^{x−1} +d^k_i. Using P2, +d^k_i ≥ +D^{k+1}_i for k<x−1 and +d^{x−1}_i ≥ max{+D^x_i, dem(f)}; hence the per-link load is at least S+max{+D^x_i, dem(f)}−+D^1_i, where S=Σ_{k=1}^{x−1}+D^k_i. The rejection inequality gives S+max{+D^x_i, dem(f)} > pL, and L ≥ max demand leaving I_i gives +D^1_i ≤ L, so the per-link load is > pL−L = (p−1)L. The manuscript should state this per-link version explicitly; with that repair, the 167/165 coefficient argument goes through.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies minimum-congestion routing of unsplittable flows in unfolded Clos networks. It claims three main results: (i) an offline polynomial-time algorithm that both guarantees congestion at most 9/5 and approximates the optimum congestion within factor 9/5 (Theorem 2.1, proved as Theorems 4.1 and 4.6); (ii) offline lower bounds showing that some instances have optimum congestion at least 3/2 and that it is NP-hard to approximate within any factor below 3/2 even for demands 1 and 1/2 (Theorems 2.2, 2.3, and Corollary 2.4); and (iii) an online lower bound of 2 for deterministic and randomized algorithms, even with unit demands, giving a strict offline/online separation (Theorems 2.5 and 2.6, proved in Section 6). The offline algorithm routes a demand-dependent subset of flows in a first phase using a Melen--Turner-style matching decomposition and routes the remaining flows greedily in a second phase, with a threshold set to 9/5 times a lower bound L on the optimum.","tokens_in":22747,"tokens_out":6888,"duration_ms":70639,"significance":"If the proofs are correct, the paper's main contribution is substantial: it breaks the factor-2 barrier that was previously the best known worst-case congestion and approximation for unsplittable routing in Clos networks, and it shows a clean separation between offline and online settings. The lower-bound parts of the paper are particularly solid: the cross-gadget construction in Section 5 is elegant, the reduction from 3-edge-coloring in Theorem 5.3 is standard but carefully executed, and the online lower bound in Section 6 correctly uses Yao's principle modulo a notational slip about powers of two. The paper also gives a useful survey of the relationship to the multirate rearrangeability literature. The main risk to the central claim is a gap in the proof of Theorem 4.1 concerning the interpretation of property Q3 in Lemma 4.2; this gap appears repairable from the surrounding properties, but it must be fixed in the written proof.","major_comments":[{"comment":"The proof of Theorem 4.1 uses a per-link consequence of property Q3, but Lemma 4.2 only proves an aggregate inequality. Specifically, the final contradiction lower-bounds the total demand on links leaving I_i(f) by C·D + (N−C)(p−1)L, where the term (N−C)(p−1)L is justified only if every non-congested link leaving I_i(f) carries more than (p−1)L. The formal statement of Q3, however, proves only that Σ_{k∈[K]} +d^k_i > (p−1)L, and an aggregate sum does not control an individual link. The gap is repairable: if I_i rejected f at copy x, then copies 1,...,x−1 are full, and in the link-disjoint Phase 1 routing each full copy contributes exactly one flow to every middle switch, so every link I_iM_m carries at least Σ_{k=1}^{x−1} +d^k_i. Using P2 and the rejection inequality, this per-link load is at least S + max{+D^x_i, dem(f)} − +D^1_i > pL − L = (p−1)L, where S = Σ_{k=1}^{x−1} +D^k_i and L ≥ max demand leaving I_i. The manuscript should state this per-link version of Q3 explicitly and use it in Theorem 4.1; as written, the step is a genuine logical gap in the central proof.","section":"§4.2, Lemma 4.2 and Theorem 4.1"},{"comment":"The claimed absolute congestion bound of 9/5 is presented only as a 'straightforward generalization' of the proof of Theorem 4.1, with the remark that Claim 4.5 and the replacement of OPT by min{OPT,1} suffice. This is a central advertised result (Theorem 2.1 states congestion at most 9/5), and the modification is not fully written out: the proof of Lemma 4.2, the definition of D, and the final coefficient calculation all need to be checked in the min{OPT,1} variant. I ask the authors to include the complete modified proof, or at least the modified statements of Lemma 4.2 and the key inequalities, so that the reader can verify that the parameter choice 9/5 survives the change.","section":"§4.2, Theorem 4.6"}],"minor_comments":[{"comment":"The line 'By setting p ≜ 9/5 and q ≜ 1/3' should read q ≜ 3; the value q=1/3 is inconsistent with the theorem statement and makes expressions such as (p − 1/q) meaningless.","section":"§4.2, proof of Theorem 4.1"},{"comment":"The number of sequences is 2^S, not 2S, and the notation '2S' is used both as the exponent and as a denominator; the expected congestion should be 2 − 1/2^S. Also, Theorem 6.3 uses S=⌊R/3⌋ while Corollary 6.6 uses S=⌈R/3⌉; the two should be reconciled.","section":"§6.2, Theorem 6.3 and Corollary 6.6"},{"comment":"In the last step of the Q3 proof, the inequality +D^1_i ≤ L is attributed to P3, but it follows from the definition of L as the maximum demand leaving I_i; the citation should be corrected.","section":"§4.2, proof of Lemma 4.2, property Q3"},{"comment":"The sentence 'Let 1/Q be a flow demand, p be an approximation factor' is confusing because the parameter used in the algorithm and analysis is q, not Q; please clarify whether Q and q are the same parameter and use one symbol consistently.","section":"§4.1"},{"comment":"There are several typographical slips: 'It not hard to show' should be 'It is not hard to show', 'plausive' should be 'plausible', and the reference to 'John Hopkins University' should be 'Johns Hopkins University'.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The Q3 gap is load-bearing but appears patchable from the existing properties, and the rest of the paper is careful and convincing. I would be willing to accept after the authors supply the per-link version of Q3 and a complete proof of Theorem 4.6. The paper is a good fit for a theory-oriented networking journal, though the presentation would benefit from a consistent notation pass."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth a serious look and a serious referee. The offline result—a 9/5 upper bound, breaking the long-standing 2 from MT and Sorted Greedy—is new and plausible; the 3/2 lower bound and NP-hardness result are clean; the online lower bound of 2 via Yao is a nice separation. The cross gadget is elegant. The paper is also honest about what is open and where the gaps in the bounds remain.\n\nThe main thing to check is Theorem 4.1. Lemma 4.2's Q3 is stated in words as a per-link congestion bound, but the formal proof establishes only an aggregate sum over copies of minimum demands. The proof of Theorem 4.1 then uses the per-link version for non-congested links, and the final 167/165 coefficient depends on it. As written, that is a real gap. It does not look fatal: the stress-test sketch derives the per-link statement from P1/P2 and the rejection inequality, and if that checks out, the theorem goes through. The coefficient is close, so the missing step is load-bearing, not cosmetic. There is also a small typo where q is set to 1/3 instead of 3 in the final calculation.\n\nThe lower-bound sections look solid. The cross-gadget construction, the 3/2 congestion lower bound, and the NP-hardness reduction are believable; the online Yao argument is clean. I do not see circularity or parameter fitting, and the citations to prior work (Khan-Singh, Ngo-Vu, Hwang, Lovasz-Plummer, CKS17) are appropriate.\n\nWho this is for: networking theory people working on Clos routing, and algorithm people interested in unsplittable flow. If the Q3 repair holds, this is a publishable result with a real improvement. I would bring it to the reading group and would cite it.\n\nRecommendation: send to peer review. The gap should be fixed or explicitly patched before acceptance, but the paper deserves referee time.","headline":"A genuine step past the factor-2 barrier in unsplittable Clos routing, with solid lower bounds; one repairable proof gap in the central theorem needs fixing.","tokens_in":23335,"tokens_out":2512,"would_cite":true,"duration_ms":23970,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68M10","68Q17","68W25"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that unsplittable-flow routing in Clos networks can be guaranteed within 9/5 of optimal congestion offline, while online routing cannot beat 2.","keywords":["minimum congestion routing","unsplittable flows","Clos networks","approximation algorithms","online algorithms","lower bounds","NP-hardness","data-center networks"],"falsifier":"Simulate the proposed algorithm with $P=\\frac{9}{5}L$ and $Q=3$ across all small Clos instances (for example $N=2,3$ and $R$ up to 5) and look for a returned routing with congestion strictly above $\\frac{9}{5}$. The proof's key step is the per-link reading of Q3; any instance where that per-link bound fails while the sum bound holds would expose the gap. Equivalently, check whether the formal Q3 inequality implies the per-link congestion lower bound used to derive the coefficient $\\frac{167}{165}$.","tokens_in":22198,"feed_emoji":"🔀","tokens_out":10668,"duration_ms":103669,"temperature":0.7,"pith_summary":"This paper tackles a concrete network-engineering question: when each data-center flow must be routed along a single path, how close to the ideal congestion 1 can a routing get? It claims the old factor-2 ceiling is not fundamental. For offline routing in Clos networks with full bisection bandwidth, it gives a polynomial-time algorithm whose worst-case congestion and approximation factor are 9/5, and proves that no polynomial-time algorithm can guarantee better than 3/2 unless P=NP. In the online setting, where flows arrive one at a time, it proves a strict separation: no online algorithm, deterministic or randomized, can approximate within a factor 2. If these results hold, operators can replace today's heuristics with a provable offline guarantee below 2, but cannot hope for the same guarantee when flows must be routed on the fly.","feed_headline":"Offline flow routing: 1.8x congestion; online stuck at 2x","feed_subtitle":"A new two-phase algorithm breaks the old 2x barrier, and a matching lower bound blocks online improvement.","key_machinery":"The load-bearing mechanism is a two-phase threshold algorithm. A lower bound $L$ on the optimal congestion is computed from the largest flow demand and the average total demand at each switch; the algorithm sets $P=\\frac{9}{5}L$ and $Q=3$. Phase 1 constructs copies of each input/output switch, assigns flows to copies in decreasing demand order so that three packing properties hold, and routes the selected subset through a link-disjoint matching decomposition. Phase 2 routes every remaining flow in decreasing demand order onto the path with minimum current congestion. The analysis uses properties Q1–Q3: Phase 1 congestion is bounded, every flow above one-third of the optimum is captured in Phase 1, and rejected flows force enough residual load to make the final contradiction stick. The lower-bound arguments rest on two structural gadgets: a cross gadget whose unique congestion-1 routing forces a diagonal assignment of flows, and two prefix-sharing unit-demand sequences whose unique good routings disagree, which the minimax principle converts into a randomized lower bound.","core_discovery":"The central claim is that minimum congestion routing of unsplittable flows in full-bisection Clos networks admits a 9/5 approximation computable in polynomial time, breaking the factor-2 barrier of the standard two-factor heuristics. The paper proves Theorem 2.1 by a two-phase algorithm: Phase 1 copies each top-of-rack switch, packs flows with large demands into copies so that a matching-based decomposition yields a low-congestion routing, and Phase 2 routes the remaining flows greedily on least-congested paths; the threshold is P=9/5 times a lower bound L on the optimum, with Q=3 separating large from small demands. It further proves that some sets of flows force congestion at least 3/2, that deciding whether congestion 1 is achievable is NP-complete when demands are 1 or 1/2, and hence that no polynomial-time algorithm approximates below 3/2 unless P=NP. Finally, for online routing it proves that every deterministic or randomized algorithm has a unit-demand sequence with congestion at least 2, matching the offline guarantee's worst case and separating the settings.","pith_inferences":["The 9/5-to-3/2 gap is the paper's own open question; a natural next design is a finer threshold or a third phase that could push the two-phase scheme toward 3/2, or a stronger gadget that raises the lower bound.","The online lower bound is proven for unit demands, while the paper notes an upper bound of 3 from an unsorted greedy argument for general demands; pinning down the exact online factor for arbitrary demands is an adjacent problem this paper leaves open.","The cross-gadget construction isolates exactly the packing constraints that make unsplittable routing hard, so it could serve as a benchmark family for testing practical traffic-engineering heuristics and load balancers.","If future transport protocols allow a limited number of split paths per flow, the threshold design suggests a trade-off curve between split path count and achievable congestion, with 9/5 and 3/2 as natural anchor points."],"forward_implications":["Offline, operators can route unsplittable flows with a provable worst-case congestion of 9/5 instead of 2, without splitting any flow.","No polynomial-time offline algorithm can improve the guarantee to below 3/2 unless P=NP, so the remaining gap to close is between 9/5 and 3/2.","Online routing is strictly harder: every online algorithm, even randomized, has a unit-demand sequence with congestion 2, so the offline improvement cannot be carried over online without re-routing or batching.","For unit-demand flows the offline problem remains easy: a congestion-1 routing is found by matching decomposition, and the 3/2 obstruction appears only once half-unit demands are allowed."],"supporting_citations":[{"why":"Together they provide the link-disjoint routing theorem for unit-demand flows and the bipartite matching decomposition that Phase 1 relies on.","marker":"[Hwa83, LP09]"},{"why":"Supplies the flow-to-ToR-copy mapping and link-disjoint routing procedure that the algorithm's Phase 1 adapts, along with the factor-2 worst case to improve.","marker":"[MT89]"},{"why":"Gives the Sorted Greedy min-congestion-path rule used in Phase 2 and the factor-2 worst case it must escape.","marker":"[AFRR+10]"},{"why":"Provides the NP-completeness of 3-edge-coloring used in the reduction proving that no approximation factor below 3/2 is possible unless P=NP.","marker":"[Kar72]"},{"why":"Supplies the minimax principle that extends the deterministic online lower bound to randomized algorithms.","marker":"[Yao77]"},{"why":"States the randomized-algorithms version of the minimax principle applied in the online lower-bound proof.","marker":"[MR95]"},{"why":"Introduces the two-phase threshold routing idea on which the new algorithm's structure is modeled.","marker":"[KS15]"}],"fun_headline_variants":["Offline flow routing: 1.8x congestion; online stuck at 2x","Offline routing hits 1.8x; online can't go below 2x","Unsplittable flows: offline 1.8x, online lower bound 2x","Data-center flows: offline 1.8x, online 2x barrier stands","New offline algorithm: 1.8x congestion, online lower bound 2x"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The 9/5 guarantee stands on reading Lemma 4.2's property Q3 as saying that every individual link incident to a switch that rejects a flow carries more than the baseline load, whereas the lemma's stated inequality only proves the total across that switch's copies exceeds the baseline.","fun_headline_variants_meta":{"raw":{"variants":["Offline flow routing: 1.8x congestion; online stuck at 2x","Offline routing hits 1.8x; online can't go below 2x","Unsplittable flows: offline 1.8x, online lower bound 2x","Data-center flows: offline 1.8x, online 2x barrier stands","New offline algorithm: 1.8x congestion, online lower bound 2x"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000634,"raw_usage":{"total_tokens":2992,"prompt_tokens":1080,"completion_tokens":1912,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":696,"completion_tokens_details":{"reasoning_tokens":1797}},"tokens_in":696,"tokens_out":1912,"duration_ms":14697,"temperature":1.0,"reasoning_tokens":1797,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T23:44:58.970946+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate the proposed algorithm with $P=\\frac{9}{5}L$ and $Q=3$ across all small Clos instances (for example $N=2,3$ and $R$ up to 5) and look for a returned routing with congestion strictly above $\\frac{9}{5}$. The proof's key step is the per-link reading of Q3; any instance where that per-link bound fails while the sum bound holds would expose the gap. Equivalently, check whether the formal Q3 inequality implies the per-link congestion lower bound used to derive the coefficient $\\frac{167}{165}$.","supporting_citations":[],"review_version":1}