{"id":"f65ed136-a338-44a7-8aa6-dc4fd9d83779","arxiv_id":"2501.09293","paper_version":7,"verdict":"REJECT","confidence":"LOW","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"Claims a 1.5-approximation algorithm for makespan-minimizing coflow scheduling in heterogeneous parallel networks, but the proof relies on a schedule order that the stated algorithms never implement.","lead":"This paper claims new scheduling algorithms for data-center coflow transfers across multiple parallel network switches, with a best theoretical worst-case guarantee of 1.5 times the optimal makespan. The main proof, however, analyzes a scheduling rule the algorithms do not actually run, and the paper's abstract and body describe different problems.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.1's rounding bound is false: assigning each flow one time label does not control BvN port loads; a 2x2 all-ones instance gives expected makespan 1.875 vs 1.5·LP, refuting Theorem 4.2.","rationale":"The reader's weakest assumption identifies the same root cause: Lemma 4.1 analyzes a schedule ordered by the sampled labels t, whereas Algorithm 2 actually runs the BvN schedule on per-core aggregated demands, and the labels t are not used. Our stress test shows this is not merely a missing justification; the claimed approximation ratio is false. The 2x2 all-ones instance has LP optimum 1, yet Algorithm 2 with a fractional optimal LP solution has expected makespan 1.875, so Theorem 4.2 is contradicted. The derivation of the failure is purely combinatorial and does not rely on any external consensus or on the abstract/body mismatch, although that mismatch independently complicates the submission. The BvN decomposition itself is standard and is not the source of the error; the error is in the randomized-rounding analysis that converts per-flow time labels into a bound on actual port loads. Because the central contribution is the 1.5-plus-epsilon guarantee and that guarantee fails on a small instance, the REJECT verdict is unchanged. The recommendation is UNCHANGED rather than a new verdict because the reader already reached REJECT, and this analysis strengthens rather than alters that conclusion.","tokens_in":18460,"tokens_out":22970,"duration_ms":247948,"concrete_test":"Run Algorithm 2 on the 2x2 all-ones single-coflow instance with m=2 unit-speed cores and the fractional LP optimum y_{ijk,p,t}=1/2 for p=1,2 and t=0. Enumerate the 2^4 assignments of the four flows to the two cores; for each assignment compute the aggregate demand matrix on each core and let Cmax be the larger of the two BvN makespans, i.e. max(rho(D_1), rho(J-D_1)). The average over the 16 outcomes is 1.875, exceeding 1.5. This directly refutes the expected-makespan claim of Theorem 4.2 for a valid optimal LP solution. A symbolic re-derivation of Lemma 4.1 for this instance confirms the failure: the probability-weighted predecessor load on a port is bounded via t+1/2, but the total volume of flows on that port in the BvN schedule is not controlled by the sampled label.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The decisive flaw is in Lemma 4.1, on which Theorems 4.2, 5.2, 6.1, and 7.2 depend. Algorithm 2 rounds each flow to a switch-time pair (p,t), then ignores t: line 4 aggregates all flows assigned to p and runs the BvN schedule, whose makespan is the maximum port load of the aggregate demand D_p. The lemma instead bounds the completion time of a fixed 'last' flow by d_{ijk}/s_p plus the probability-weighted volumes of flows whose sampled label is smaller than t. This substitutes the LP's fractional processing time sum_ell y_{...ell} for the total volume of flows whose label precedes t. After rounding, these are not the same: a flow with a large label still contributes its whole volume to the port load and can delay the last flow. The label is also random, so 'the last flow is (i,j,k)' cannot be fixed outside the expectation. A concrete refutation: m=2 unit-speed cores, one coflow with demand matrix [[1,1],[1,1]]. The LP optimum is 1, e.g. split each flow 1/2 to each core at t=0. If Algorithm 2 receives this optimal LP solution, each of the four flows goes to core 1 or core 2 with probability 1/2. The actual makespan is max(rho(D_1), rho(J-D_1)); it is 1 exactly when D_1 is a permutation matrix (2 of the 16 equally likely outcomes) and 2 otherwise. Therefore E[Cmax] = 30/16 = 1.875, which is strictly greater than 1.5 = 1.5·OPT_LP. So Theorem 4.2's central guarantee is false for a legitimate optimal LP solution. The same label-versus-volume gap appears in the interval-indexed proof of Theorem 6.1.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript studies makespan minimization for preemptive coflow scheduling across m heterogeneous network cores. It introduces a time-indexed linear programming relaxation, a randomized rounding step that assigns each flow to a single core and a time label, and then applies Birkhoff-von Neumann decomposition per core to obtain a non-splitting schedule. The paper claims a randomized 1.5-approximation in pseudo-polynomial time, a derandomized 1.5+1/(2LB) algorithm, and polynomial-time 1.5+epsilon variants, improving on the previously known 2+epsilon bound. The central technical step is Lemma 4.1, which bounds the expected makespan of the algorithm's output by analyzing a hypothetical schedule in which flows are transmitted in non-decreasing order of their sampled time labels.","tokens_in":18728,"tokens_out":5861,"duration_ms":55967,"significance":"If the 1.5 bound were correct, this would be a meaningful improvement over the best known 2+epsilon approximation for heterogeneous parallel coflow scheduling, and the derandomization and interval-indexed variants would be useful contributions. However, the main proof analyzes a schedule that the algorithm does not produce, and there is a concrete instance on which the claimed 1.5 bound is violated. The paper therefore does not establish its central claim, and the same flaw propagates to all four main theorems (Theorems 4.2, 5.2, 6.1, and 7.2).","major_comments":[{"comment":"The analysis in Lemma 4.1 does not bound the makespan of the schedule produced by Algorithm 2. Algorithm 2 (line 4) aggregates all flows assigned to each core p and runs Algorithm 1, whose makespan is the maximum row/column load of the aggregated demand matrix D_p. The proof of Lemma 4.1 instead bounds the expected load on a port by considering flows in non-decreasing order of their sampled time label t and using the probability that another flow receives a smaller label. These are different objects: in the BvN schedule, a flow with a large label contributes its entire volume to the port load regardless of its label, whereas in the analyzed t-order schedule it is delayed. The manuscript itself acknowledges this after Algorithm 2: 't is not directly utilized in the algorithm; it serves solely as a tool for our analysis.' That admission is precisely the problem, because the lemma's bound depends on the t-order, so the analyzed schedule is not the algorithm's output. Additionally, the proof fixes 'the last completed flow (i,j,k)' before the random choices are made, but the identity of the last flow depends on the rounding outcomes, so the conditioning is not a valid WLOG step.","section":"Section 4, Algorithm 2 and Lemma 4.1"},{"comment":"The claimed 1.5-approximation is false for a valid instance. Take m=2 unit-speed cores and a single coflow with demand matrix [[1,1],[1,1]] on two input and two output ports. The LP optimum is C*_max = 1, achieved by setting y_{ijkp0} = 1/2 for each of the four flows and each core p. Algorithm 2 then assigns each flow independently to core 1 or core 2 with probability 1/2. For a given assignment, the makespan is max(rho(D_1), rho(D_2)), where rho is the maximum row or column sum of the aggregate matrix on that core. This value is 1 only in the 2 of 16 equally likely assignments where the flows on each core form a permutation matrix; in the remaining 14 assignments the makespan is 2. Hence E[Cmax] = (2*1 + 14*2)/16 = 30/16 = 1.875 > 1.5 = 1.5*C*_max. This directly refutes Theorem 4.2 and, because Theorems 5.2, 6.1, and 7.2 rely on the same lemma and the same analysis, the counterexample invalidates those results as well.","section":"Theorem 4.2"},{"comment":"The inequality Ep,t[Ci] <= dijk/sp + (t+1/2) in the proof of Lemma 4.1 is derived by summing, over other flows on the same port, the product of each flow's volume and the probability that it is assigned a label smaller than t. This quantity bounds the load in a hypothetical ordered schedule, but in the actual BvN schedule the load contributed by a flow is independent of its label: every flow assigned to the core contributes its full volume to its input and output ports. Therefore the conditional expectation computed in the lemma is not an upper bound on the conditional makespan of the algorithm. This is not a minor gap but a load-bearing mismatch between the object analyzed and the object produced.","section":"Section 4, proof of Lemma 4.1"}],"minor_comments":[{"comment":"The proof of Theorem 7.3 says 'Following the same proof steps as in The proof of Theorem 7.3 yields this theorem,' which is self-referential and should instead refer to the proof of Theorem 7.2 or to the argument that precedes it.","section":"Section 7, Theorem 7.3"},{"comment":"Several formulas contain typesetting artifacts, such as '1.5 + 1 2·LB' and '1Pm p=1 sp', which make the intended expressions, likely 1.5 + 1/(2LB) and 1/(sum_p s_p), hard to read and should be corrected.","section":"Sections 5 and 7"},{"comment":"The quantity Pr_{p,t}(i',j',k') is described as a probability that another flow is scheduled before (i,j,k), but the actual algorithm does not schedule flows in this order. The notation should be clarified, or the paper should explicitly state that this is only an analysis artifact; currently the text alternates between calling it a probability and using it to bound port loads.","section":"Section 4, definition of Pr_{p,t}"}],"recommendation":"reject","confidential_remarks":"The concrete counterexample given in the major comments is decisive: it shows the main theorem is false for a legitimate optimal LP solution, and the flaw is not a minor proof gap but a mismatch between the analyzed t-order schedule and the BvN schedule produced by the algorithm. The same analysis underlies all four main theorems, so the paper's central contribution is not established. I recommend rejection. The paper could potentially be reworked by changing the algorithm to actually schedule according to the sampled labels, or by designing a rounding scheme that directly controls port loads, but that would be a substantially different paper."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the paper claims a 1.5-expected makespan approximation for preemptive coflow scheduling in heterogeneous parallel networks, improving the best-known 2+epsilon. That bound is genuinely new relative to the cited literature, and the machinery—interval-indexed LP, randomized rounding, Birkhoff-von Neumann decomposition, conditional-expectation derandomization—is assembled cleanly. But the central proof does not analyze the algorithm that is run, and the main theorem is false as stated.\n\nWhat is new: the 1.5 ratio, plus deterministic 1.5+1/(2LB) and polynomial 1.5+epsilon variants. None of these appear in prior work. The paper is not circular; self-citations are used as baselines and the LP+BvN argument is independent.\n\nThe soft spot is load-bearing. Algorithms 2–5 randomize each flow to a switch-time pair (p,t), then throw t away: line 4 aggregates all flows on each core and schedules via BvN. The analysis in Lemma 4.1 instead schedules each port in non-decreasing t and bounds the completion of a fixed 'last' flow. Those are different schedules. A t-order schedule can serialize flows that a BvN schedule transmits in parallel, and the proof substitutes the fractional LP volume of flows with smaller label for the total volume that actually lands on the port. The label is also random, so conditioning on a fixed last flow outside the expectation does not work.\n\nThis is not a stylistic quibble. Take m=2 unit-speed cores and one coflow with demand matrix [[1,1],[1,1]]. The LP optimum is 1 (split each flow 1/2 on each core). Algorithm 2 then sends each of the four flows to core 1 or core 2 with probability 1/2. The makespan is 1 only when one core receives a permutation matrix—2 of the 16 equally likely outcomes—and is 2 otherwise. Expected makespan is 15/8=1.875, strictly above 1.5·OPT. So Theorem 4.2 is false, and Theorems 5.2, 6.1, and 7.2 inherit the failure.\n\nThere are smaller issues too: the final algebra in Theorem 6.1 actually gives 1.5+eta/4, not 1.5+eta/2; that one is harmless. The arXiv metadata abstract describes a different paper (non-splitting coflows in hybrid EPS/OCS networks with ratios involving tau and m), while the full text is preemptive makespan scheduling. That mismatch is a red flag for editorial handling.\n\nWho this is for: someone working on coflow scheduling might read the technique sections for the standard toolkit, but the claimed result is not supported. It still deserves a serious referee: the flaw is subtle, the counterexample is small, and if the author can make the analysis match the algorithm, or modify the algorithm to match the analysis, the 1.5 aim may be salvageable. As it stands, reject, but not because the paper is unserious.","headline":"The claimed 1.5-approximation is not established; the paper analyzes a t-priority schedule that the algorithm never runs, and a simple 2x2 instance refutes the central theorem.","tokens_in":19378,"tokens_out":4459,"would_cite":false,"duration_ms":42824,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25","90B35"],"pacs":[],"model":"deepseek-v4-flash","headline":"Randomized rounding of an interval-indexed LP relaxation yields a $1.5+\\epsilon$ approximation for coflow makespan on heterogeneous parallel networks, improving the previous $2+\\epsilon$ bound.","keywords":["coflow scheduling","makespan minimization","approximation algorithm","heterogeneous parallel network","Birkhoff–von Neumann decomposition","interval-indexed LP relaxation","randomized rounding","derandomization"],"falsifier":"Run Algorithm 2 on a small heterogeneous instance, enumerate all outcomes of the random switch-time assignments, and compare $\\mathbb{E}[\\max_p \\rho(D_p)]$, the expected makespan of the actual Birkhoff–von Neumann schedule (which on core $p$ is exactly the port load $\\rho(D_p)$), against $1.5\\,C^*_{\\max}$ from the LP; any instance where the former exceeds the latter would refute Theorem 4.2 for the algorithm as written.","tokens_in":18099,"feed_emoji":"⏱️","tokens_out":12095,"duration_ms":121556,"temperature":0.7,"pith_summary":"The paper studies makespan-minimizing coflow scheduling on heterogeneous parallel networks, where $m$ network cores with different link speeds operate simultaneously and a coflow finishes when its last flow finishes. It claims that an interval-indexed LP relaxation with randomized rounding, followed by Birkhoff–von Neumann scheduling on each core, yields an expected makespan of at most $1.5+\\epsilon$ times the optimum in polynomial time, and that conditional-expectation derandomization gives a deterministic approximation of $1.5+\\frac{1}{2\\cdot LB}+\\epsilon$ (or $1.5+\\epsilon$ when flows are large). These bounds improve the previously known $2+\\epsilon$ factor for this setting. The result matters because coflow scheduling abstracts data-center communication, and better approximation guarantees translate to more predictable completion times for distributed jobs.","feed_headline":"LP rounding yields 1.5+ε-approximate coflow schedules","feed_subtitle":"Randomized and deterministic schedules improve the best known bound on coflow makespan from 2+ε to 1.5+ε.","key_machinery":"The load-bearing mechanism is a two-part construction. First, an interval-indexed LP relaxation (5) is solved; its variables $y_{ijkp\\ell}$ encode, for the interval $\\ell$, the fraction of flow $(i,j,k)$ that will be sent over network core $p$, with capacity constraints per port and per interval, and with completion-time lower bounds $C_{ijk}$ defined through the functions $f(i,j,k,p,\\ell)$. Second, randomized rounding assigns each flow to a switch-interval pair $(p,\\ell)$ with probability $s_p y_{ijkp\\ell}|I_\\ell|/d_{ijk}$, after which all flows assigned to core $p$ are aggregated into one demand matrix $D_p$ and transmitted by Birkhoff–von Neumann decomposition (Algorithm 1). The named identity doing the work is the Birkhoff–von Neumann theorem: every doubly stochastic matrix is a convex combination of permutation matrices, so the augmented demand matrix $\\tilde D_p/\\rho(D_p)$ becomes a weighted list of perfect matchings, each executed for one time slot; the schedule length on core $p$ is exactly the port load $\\rho(D_p)$. The $1.5$ factor emerges because the expected completion time of the last flow is bounded by $(t+\\frac12)$ plus half its transmission time, which matches the LP's lower-bound expression.","core_discovery":"The paper's central claim is that the makespan of preemptive coflow scheduling in heterogeneous parallel networks can be approximated within a factor of $1.5$ by a randomized rounding of the LP relaxation, and that exponential interval indexing reduces this to a polynomial-time $1.5+\\epsilon$ randomized algorithm; derandomization by conditional expectations gives deterministic algorithms with ratios $1.5+\\frac{1}{2\\cdot LB}$ and $1.5+\\frac{1}{2\\cdot LB}+\\epsilon$, with the $\\epsilon$ term disappearing when the minimum flow is at least $(1-\\eta)/\\eta$. The prior best known bound was $2+\\epsilon$. The construction assigns every flow to a switch-time pair according to the LP solution, bundles the flows on each core into a single demand matrix, and uses Birkhoff–von Neumann decomposition to transmit that matrix in a number of time slots equal to its maximum port load; the proof then bounds the expected completion time of the final flow by $1.5$ times the LP optimum.","pith_inferences":["Beyond the paper: the proof analyzes an ordering of flows by the LP-assigned time $t$, but the implemented Birkhoff–von Neumann schedule can transmit disjoint flows in parallel; the gap between these two schedules is not quantified, so an empirical check on adversarial instances would be valuable.","Beyond the paper: the same interval-indexed rounding scheme may extend to total weighted coflow completion time, though the paper only addresses makespan.","Beyond the paper: because the deterministic ratio improves as flow sizes grow, practical data-center workloads with large transfers could see the stronger $1.5+\\epsilon$ guarantee, while small-flow workloads would carry the additive $1/(2\\cdot LB)$ term."],"forward_implications":["If correct, the $1.5+\\epsilon$ polynomial-time bound replaces $2+\\epsilon$ as the best known guarantee for heterogeneous parallel coflow makespan.","The deterministic variant provides the same asymptotic ratio without random bits, and its additive $1/(2\\cdot LB)$ term vanishes as port loads grow, giving $1.5+\\epsilon$ when the minimum flow size is at least $(1-\\eta)/\\eta$.","The interval-indexed LP uses only $O(\\log T)$ intervals, so the algorithms' running times are polynomial in the input size rather than in the total volume of data.","Each core's schedule is a sequence of permutation matchings produced by Birkhoff–von Neumann decomposition, so it can be executed directly on nonblocking switch hardware."],"supporting_citations":[{"why":"Supplies Algorithm 1, the Birkhoff–von Neumann schedule that transmits one coflow in exactly its maximum port load.","marker":"[18]"},{"why":"States the Birkhoff–von Neumann decomposition theorem used to turn an augmented demand matrix into permutation matrices.","marker":"[17]"},{"why":"Contributes the randomized-rounding and conditional-expectation derandomization technique for LP scheduling.","marker":"[19]"},{"why":"Is the previous $2+\\epsilon$ approximation result for heterogeneous parallel networks that the paper improves.","marker":"[5]"},{"why":"Defines coflows and the completion-time objective, establishing the problem the paper solves.","marker":"[10]"}],"fun_headline_variants":["First provable guarantees for non-splitting coflow scheduling","Non-splitting coflow scheduling gets first approximation algorithms","Approximation algorithms for non-splitting coflow in hybrid networks","Provable scheduling for non-splitting coflows in heterogeneous nets"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Everything rests on treating the makespan as the larger of the two port loads of an arbitrarily chosen last flow and on analyzing the schedule in LP-assigned $t$ order; the algorithm actually schedules by Birkhoff–von Neumann matchings, whose makespan is the maximum load over all ports, so if those two views diverge the $1.5$ guarantee may not apply to the real output.","fun_headline_variants_meta":{"raw":{"variants":["First provable guarantees for non-splitting coflow scheduling","Non-splitting coflow scheduling gets first approximation algorithms","Approximation algorithms for non-splitting coflow in hybrid networks","Provable scheduling for non-splitting coflows in heterogeneous nets"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00095,"raw_usage":{"total_tokens":4112,"prompt_tokens":1059,"completion_tokens":3053,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":675,"completion_tokens_details":{"reasoning_tokens":2981}},"tokens_in":675,"tokens_out":3053,"duration_ms":21727,"temperature":1.0,"reasoning_tokens":2981,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T20:09:02.488607+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 2 on a small heterogeneous instance, enumerate all outcomes of the random switch-time assignments, and compare $\\mathbb{E}[\\max_p \\rho(D_p)]$, the expected makespan of the actual Birkhoff–von Neumann schedule (which on core $p$ is exactly the port load $\\rho(D_p)$), against $1.5\\,C^*_{\\max}$ from the LP; any instance where the former exceeds the latter would refute Theorem 4.2 for the algorithm as written.","supporting_citations":[{"cited_title":"Diagonals of doubly stochastic matrices,","cited_arxiv_id":null,"evidence_quote":"States the Birkhoff–von Neumann decomposition theorem used to turn an augmented demand matrix into permutation matrices."},{"cited_title":"Scheduling unrelated machines by randomized rounding,","cited_arxiv_id":null,"evidence_quote":"Contributes the randomized-rounding and conditional-expectation derandomization technique for LP scheduling."},{"cited_title":"Improved approximation coflows scheduling algorithms for minimizing the total weighted completion time and makespan in heterogeneous parallel networks,","cited_arxiv_id":null,"evidence_quote":"Is the previous $2+\\epsilon$ approximation result for heterogeneous parallel networks that the paper improves."}],"review_version":2}