{"id":"5709ff7e-38a0-46b5-a211-0ef8b0edc79c","arxiv_id":"2501.02952","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":1,"one_line_summary":"An online edge-cloud task offloading algorithm using Lyapunov optimization, matching, and rounding is proposed to minimize device energy while keeping queues stable.","lead":"The paper proposes an online algorithm that decides, second by second, whether each user task runs on the phone, an edge server, or a cloud server, in order to save battery while meeting delay limits. It is a read for network engineers who want a polynomial-time offloading policy for dense edge computing systems.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 9's Copt+B/V bound rests on an unproven per-slot optimality premise: Algorithm 3 has no optimality or suboptimality-gap guarantee for P'', so Eq. (47) does not follow.","rationale":"The reader's weakest assumption identifies exactly the load-bearing weakness I find: Theorem 9's optimality-gap bound requires per-slot near-optimal decisions, but Algorithm 3 is a heuristic assembled from swap matching, remove-action refinement, relaxation plus dependent rounding, and a capacity sweep, with no optimality or bounded-gap proof. This is not merely a missing appendix; the paper itself states in Section 5.1 that the method achieves 'a sub-optimal solution with polynomial time complexity,' and nothing in Sections 5.2.1-5.2.3 quantifies that suboptimality. The Tammer decomposition citation can justify an exact decomposition, not the heuristic solvers applied to the subproblems. The additional issues noted by the reader (all theorem proofs deferred to a nonexistent appendix, no released code or data, simulation plots without error bars) reinforce the decision, but the decisive concern is the unproven per-slot solver. Because the central claim as stated is neither proved nor independently verifiable, the REJECT verdict is appropriate; if the authors later supply a per-slot suboptimality bound or replace Algorithm 3 with a solver that has one, and provide the missing proofs and reproducible code, a CONDITIONAL acceptance could be reconsidered.","tokens_in":28661,"tokens_out":6851,"duration_ms":63696,"concrete_test":"Fix one MEC server with U = 10 UDs, draw random task sizes, channel gains, and queue backlogs Q_E, Q_C, Z_E, Z_C, and fix V. Enumerate all feasible binary decisions (x_u^m, x_u^{m->c}) with x_u^{m->c} <= x_u^m; for each, compute the optimal A by Eq. (29) and the exact P'' objective (22). Run Algorithm 3 on the same instances and record the relative gap to the exact minimum. Repeat for at least 1000 random instances. If the typical or maximum gap is not uniformly small, or grows with U, the per-slot optimality premise of Theorem 9 fails; if it is small, the test would show only empirically that the missing analysis is the decisive obstruction, not prove the bound.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central guarantee (Theorem 9, Eq. 47) is derived from the standard Lyapunov drift-plus-penalty argument, which requires that in every slot the chosen action minimizes the conditional drift-plus-penalty expression, or is within a uniform additive constant of the minimum. The solver actually used is the heuristic Algorithm 3: Algorithm 1 performs random-initialized swap matching until no blocking pair exists and then applies a remove-action refinement; Algorithm 2 solves a continuous relaxation of the queue-stability subproblem and applies dependent rounding; Algorithm 3 sweeps the connection capacity n and selects the best objective value among those n. None of these steps is shown to solve P'' (Eq. 22) or to have any suboptimality bound. The Section 5.2.1 appeal to the Tammer decomposition preserving optimality [31] addresses a different question: even if the decomposition is exact, the proposed algorithms do not solve the decomposed subproblems to optimality. Algorithm 1's swap-matching outcome is merely pairwise stable under externalities, which does not imply global optimality, and the remove-action refinement changes the matching after stability is reached. Algorithm 3's capacity sweep only evaluates the heuristic for different allowed matching sizes. Thus the per-slot additive-optimality premise of Theorem 9 is unverified; without it, Eq. (47) does not follow from the presented material. The missing 'Appendix ??' proofs cannot repair this, because the gap is algorithmic, not merely a missing derivation.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a hierarchical edge-cloud MEC architecture and formulates EEDAOP, a problem that minimizes time-average UD energy consumption under task-deadline and long-term queuing-delay constraints. The authors apply Lyapunov drift-plus-penalty optimization to convert the time-coupled problem into a per-slot problem P'', then decouple P'' via a claimed Tammer decomposition, solve the communication-resource subproblem in closed form (Eq. (29)), and solve the task-offloading subproblem with a two-stage heuristic that combines swap matching, convex relaxation with dependent rounding, and a capacity sweep (Algorithms 1-3). The main analytical claims are that OJCTA has worst-case complexity O(LU^3) (Theorem 8) and that its time-average energy is bounded by Copt + B/V (Theorem 9, Eq. (47)), with simulation results reported in Section 6.","tokens_in":28890,"tokens_out":6595,"duration_ms":68133,"significance":"If the analytical claims were fully established, OJCTA would be a valuable polynomial-time online policy with a rigorous near-optimality gap for a realistic edge-cloud MEC setting. The paper has several genuine strengths: the Lyapunov transformation is the standard and appropriate tool, the closed-form bandwidth allocation in Eq. (29) is a plausible result for the stated convex subproblem, and the simulation study compares against multiple external baselines rather than being fitted to reproduce known results. However, the central contribution is the optimality bound in Theorem 9, and that bound is not supported by the presented material: every theorem proof is deferred to a nonexistent appendix, and the per-slot solver is a heuristic with no demonstrated optimality or approximation guarantee. The empirical section does not compensate because it does not compare against the claimed bound. The paper would need a substantially different argument, either an approximation guarantee for the per-slot heuristic or a weakened claim, to make the main theorem load-bearing.","major_comments":[{"comment":"The bound in Eq. (47) is the standard Lyapunov drift-plus-penalty result and is valid only if the per-slot action minimizes the conditional drift-plus-penalty expression, or is within a uniform additive constant of the minimum. The actual per-slot solver is Algorithm 3, which combines the swap-matching heuristic of Algorithm 1, the convex-relaxation plus dependent rounding of Algorithm 2, and a capacity sweep. None of these components is shown to solve P'' (Eq. (22)) or to have any suboptimality bound. The appeal to Tammer decomposition in §5.2.1 does not fill this gap, because even if the decomposition were exact, Algorithms 1-3 do not solve the decomposed subproblems to optimality. Consequently, Eq. (47) does not follow from the presented arguments.","section":"§5.3.2, Theorem 9, Eq. (47)"},{"comment":"Every theorem in the paper, including the central Theorem 9 and the complexity claim Theorem 8, is proved only in \"Appendix ?? of the supplemental material,\" which is absent from the manuscript. As submitted, the paper contains no verifiable proof for any of its analytical claims; the proofs are not merely deferred to a real appendix but to a placeholder that does not exist. This alone prevents acceptance in the present form.","section":"§5.1-§5.3, Theorems 1-9"},{"comment":"The paper states that the energy minimization subproblem P'''2.1 is NP-hard, then proposes a matching-based heuristic without an approximation guarantee. Pairwise stability of the swap matching plus the \"remove action\" refinement does not imply global optimality of the resulting offloading decisions, and Algorithm 3 only evaluates this heuristic at different allowed matching sizes. Since Theorem 9 requires per-slot decisions that are optimal or within a bounded gap, the mismatch between the heuristic solver and the per-slot optimum is load-bearing and is not addressed anywhere in the manuscript.","section":"§5.2.3, Theorem 5, Algorithm 1"},{"comment":"The evaluation reports average energy and queue-delay curves without confidence intervals, standard deviations, or multiple random seeds, and it does not compare the observed time-average energy consumption with the theoretical bound Copt + B/V from Eq. (47). As a result, the simulations cannot substitute for the missing analytical guarantee of Theorem 9, and the empirical claims should be interpreted with caution.","section":"§6, Simulation Results"}],"minor_comments":[{"comment":"The coefficient in Eq. (7) is written as ζk, but the model defines it as ζu for UD u; the notation should be consistent.","section":"§3.3, Eq. (7)"},{"comment":"The summand in the penalty term contains E^{loc}_k(t), which should be E^{loc}_u(t) with the correct index; also \"for all all possible\" is a typo.","section":"Eq. (20), Theorem 1"},{"comment":"There are several notation inconsistencies between sets and indices: Um(t) is sometimes used before being defined, and the objective in Eq. (22) uses k in sums where u is the intended index; the sets U^S_m and U^C_m are defined but some equations later reuse k as an index instead of u.","section":"§3.4 and §5.2.1"},{"comment":"The queue stability subproblem includes \"xm→c_u ≤ (xm_u)^*\" as (41b), but since the domain is already restricted to u ∈ U^O_m (where (xm_u)^* = 1), this constraint is redundant; this should be clarified.","section":"§5.2.3, Eq. (41)"},{"comment":"The table uses parameter names Z and Iu, while the text uses ρ and s_u(t); these should be aligned to avoid confusion.","section":"Table 1 and §6"},{"comment":"Algorithm 2 line 16 writes (xm→c_{u2}) without the prime used elsewhere in the update, and Algorithm 3 does not explicitly define how it obtains the final continuous resource allocation A(t) beyond the closed-form Eq. (29).","section":"Algorithms 2 and 3"}],"recommendation":"reject","confidential_remarks":"The manuscript appears to be an incomplete submission: all proofs point to a missing \"Appendix ??\", and the central Theorem 9 rests on an unverified per-slot optimality premise for a heuristic solver. These are not presentation issues but failures to establish the paper's main claim. I recommend rejection in the present form. A substantially revised version could be reconsidered if it either (i) provides a rigorous suboptimality bound for the per-slot heuristic or (ii) explicitly weakens the claimed guarantees to align with what the algorithms actually provide, and if all deferred proofs are actually included."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a standard Lyapunov-plus-heuristic MEC paper with a reasonable problem formulation and internally consistent simulations, but the advertised guarantees don't hold as written. The architecture (UDs, MEC servers, cloud) is not new, and neither are the tools - Lyapunov drift-plus-penalty, bilateral matching, convex allocation, dependent rounding - but the specific combination, with two queues per server and virtual queues for long-term queuing delay constraints, is a legitimate new problem instance. The closed-form bandwidth allocation in Eq. (29) is a nice touch, and the simulation story is coherent: OJCTA beats the simple baselines, loses only to the energy-only ECF, and ECF blows up queues as expected. No circularity red flags; the algorithm isn't fitted to reproduce benchmarks.\n\nThe soft spots are load-bearing. All nine theorems, including the central complexity claim (Theorem 8) and the optimality gap (Theorem 9), are deferred to \"Appendix ??\", which doesn't exist in this version. That alone forces a major revision. More importantly, the stress-test is right: Theorem 9's Copt + B/V bound follows from the standard Lyapunov argument only if each per-slot action is optimal, or stays within a bounded additive gap, for the drift-plus-penalty expression. Algorithm 3 is a heuristic - swap matching until pairwise stability, a remove-action refinement, a capacity sweep, and dependent rounding - and none of these steps has a suboptimality guarantee. The appeal to Tammer decomposition [31] only preserves optimality if the subproblems are solved exactly, which they aren't. So Eq. (47) doesn't follow as written. The missing proofs are a symptom, not the root cause; the algorithmic gap is the root cause.\n\nMinor issues: no code or data release, no error bars on the plots, and the percentage improvements in Fig. 6 have no variance. These are fixable.\n\nWho is this for? A reader who wants a plausible online heuristic in a crowded field and can live without formal guarantees. If the authors supply the appendix and either prove a suboptimality bound for Algorithm 3 or honestly soften the claims to heuristic performance, this could become an acceptable systems paper. As is, I wouldn't cite the Copt + B/V bound, and I'd want the code before trusting the numbers.\n\nRecommendation: don't desk-reject outright - the formulation is coherent and worth referee time - but send it to someone who understands matching theory and Lyapunov methods, with the clear expectation that the per-slot optimality gap is the key question. If that gap isn't fixed, reject.","headline":"A coherent Lyapunov-plus-heuristic MEC paper whose central optimality bound rests on an unproven per-slot optimality premise and a missing appendix.","tokens_in":29478,"tokens_out":2486,"would_cite":false,"duration_ms":66451,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that an online Lyapunov-based policy for edge-cloud task offloading and bandwidth allocation keeps time-average user-device energy consumption within $C_{\\mathrm{opt}} + B/V$ of the offline optimum while maintaining…","keywords":["multi-access edge computing","task offloading","communication resource allocation","Lyapunov optimization","energy minimization","queuing delay","edge-cloud collaboration","online optimization"],"falsifier":"For a single randomly chosen time slot with small $U$ and $M$, solve problem $P''$ to global optimality by exhaustive enumeration over all binary offloading choices and compare that optimum with the output of Algorithm 3; if the ratio of the two objective values is not uniformly bounded across random channel states, then the proof of Eq. (47) fails, because the Lyapunov argument assumes per-slot optimality or a bounded gap.","tokens_in":28388,"feed_emoji":"⚡","tokens_out":6674,"duration_ms":69304,"temperature":0.7,"pith_summary":"The paper tackles the problem that energy-limited user devices, bandwidth-limited edge servers, and a distant cloud must jointly decide, in real time, where to process each arriving task and how to split wireless bandwidth. It formulates this as an NP-hard mixed-integer nonlinear program and then proposes an online algorithm that converts the time-coupled problem into per-slot decisions using Lyapunov drift-plus-penalty optimization. The central claim is a quantitative guarantee: the time-average user-device energy consumption of the proposed policy stays within $C_{\\mathrm{opt}} + B/V$ of the offline optimum, where $C_{\\mathrm{opt}}$ is the best possible value with full future knowledge, while the edge and cloud queues remain stable. If correct, this gives a causal, polynomial-time policy with a provable energy-delay tradeoff for a three-layer edge-cloud MEC system, rather than a heuristic with no performance bound.","feed_headline":"Edge-cloud offloading stays near-optimal on energy, online","feed_subtitle":"A Lyapunov-based policy decides offloading and bandwidth each slot with a proven $C_{\\mathrm{opt}} + B/V$ energy bound.","key_machinery":"The carrying mechanism is the Lyapunov drift-plus-penalty framework combined with a per-slot decomposition. Virtual queues $Z^E_m(t)$ and $Z^C_m(t)$ convert the long-term queuing-delay constraints into queue-stability constraints, and the drift-plus-penalty bound of Theorem 1 turns the time-coupled problem into a real-time per-slot problem $P''$. The per-slot problem is then decoupled by the Tammer decomposition mechanism into a convex bandwidth-allocation subproblem with a closed-form solution (Theorem 3) and an integer task-offloading subproblem solved by bilateral matching, a remove-action refinement, and dependent rounding. The central identity is the bound $\\Lambda(\\Theta(t)) \\leq B + \\sum_m (V\\,\\text{energy} + \\text{queue terms})$, whose constant $B$ and parameter $V$ reappear in the final optimality gap $C_{\\mathrm{opt}} + B/V$.","core_discovery":"The paper's central discovery, stated as Theorem 9, is that the proposed online joint communication resource allocation and task offloading approach (OJCTA) achieves a time-average user-device energy consumption no larger than $C_{\\mathrm{opt}} + B/V$, where $C_{\\mathrm{opt}}$ is the offline optimal energy consumption, $B$ is a finite constant from the Lyapunov drift bound, and $V$ is a tunable penalty parameter. The same theorem asserts that this holds while keeping the edge computing queues and cloud offloading queues strongly stable, so the long-term queuing-delay constraints are satisfied. The paper also claims that the worst-case per-slot complexity is polynomial, $O(LU^3)$, and that simulations show OJCTA outperforms the benchmark approaches in energy consumption while maintaining moderate and stable queuing delays.","pith_inferences":["If the per-slot solver were replaced by an exact solver, or by one with a proven approximation ratio, the same drift-plus-penalty machinery would convert that ratio into an explicit energy-delay tradeoff curve, which the paper leaves implicit.","The four-queue Lyapunov construction is general enough to carry other long-term constraints: adding one virtual queue per average power, bandwidth, or latency budget would extend the same proof structure to a broader class of MEC resource-management problems.","Because the dependent-rounding step preserves the total amount of data sent to the cloud, the rounding error is mostly a redistribution across users; a natural test is whether per-user fairness is affected when task sizes are highly skewed."],"forward_implications":["Time-average user-device energy consumption is within $C_{\\mathrm{opt}} + B/V$ of the offline optimum, so increasing $V$ pushes energy consumption toward the optimum at the cost of larger queue backlogs.","Edge and cloud queues are stable under the policy, so the long-term queuing-delay constraints derived from Little's law are satisfied without requiring future knowledge of task arrivals or channel states.","Each time slot only needs current queue backlogs, current task arrivals, and current channel gains, making the policy implementable online in a dynamic MEC environment.","The worst-case per-slot complexity is $O(LU^3)$, polynomial in the number of users $U$ and the capacity-sweep length $L$, so the approach scales to dense deployments.","The edge-cloud collaborative architecture and the cloud-offloading queue reduce queuing delay and energy consumption compared to edge-only baselines, according to the simulation comparisons."],"supporting_citations":[{"why":"Supplies the Lyapunov drift-plus-penalty framework used to convert the time-coupled problem into per-slot decisions and to derive the $C_{\\mathrm{opt}} + B/V$ bound in Theorem 9.","marker":"[32]"},{"why":"Tammer decomposition is cited as the mechanism that decouples the per-slot problem into communication-resource-allocation and task-offloading subproblems while preserving optimality.","marker":"[31]"},{"why":"Dependent rounding is the technique used to convert the fractional cloud-offloading solution into a binary one while preserving the total data volume sent to the cloud.","marker":"[36]"},{"why":"Bilateral matching is the basis of Algorithm 1, which determines which user associates with which server, local or MEC, in the energy-minimization stage.","marker":"[33]"},{"why":"Little's law is the standard result used to convert average queue lengths into the long-term queuing-delay constraints in Eqs. (12) and (13).","marker":"[27]"},{"why":"Convex optimization theory is used to prove convexity of the bandwidth-allocation subproblem and to justify the closed-form solution in Theorem 3.","marker":"[28]"},{"why":"Provides the single-slot-constraint (SSC) baseline that OJCTA is compared against in the energy and delay simulations.","marker":"[37]"},{"why":"Provides the no-cloud-collaboration (NCC) baseline used to demonstrate the value of the edge-cloud collaborative architecture.","marker":"[38]"},{"why":"Provides the genetic-algorithm-based joint task offloading and resource allocation baseline (GJTORA) used in the simulation comparisons.","marker":"[39]"}],"fun_headline_variants":["Lyapunov-based online offloading hits energy near-optimal bound","Online edge-cloud offloading: energy within B/V of offline optimal","Near-optimal energy, stable queues: OJCTA online policy","Online offloading achieves C_opt + B/V energy with stable queues","Edge-cloud online policy: energy bound minus B/V from optimal"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The energy guarantee holds only if the per-slot solver truly finds the best, or near-best, offloading and bandwidth choice at every slot, but the paper does not prove how close its heuristic solver gets to that best choice.","fun_headline_variants_meta":{"raw":{"variants":["Lyapunov-based online offloading hits energy near-optimal bound","Online edge-cloud offloading: energy within B/V of offline optimal","Near-optimal energy, stable queues: OJCTA online policy","Online offloading achieves C_opt + B/V energy with stable queues","Edge-cloud online policy: energy bound minus B/V from optimal"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000227,"raw_usage":{"total_tokens":1478,"prompt_tokens":960,"completion_tokens":518,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":576,"completion_tokens_details":{"reasoning_tokens":427}},"tokens_in":576,"tokens_out":518,"duration_ms":5310,"temperature":1.0,"reasoning_tokens":427,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T21:59:58.326654+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a single randomly chosen time slot with small $U$ and $M$, solve problem $P''$ to global optimality by exhaustive enumeration over all binary offloading choices and compare that optimum with the output of Algorithm 3; if the ratio of the two objective values is not uniformly bounded across random channel states, then the proof of Eq. (47) fails, because the Lyapunov argument assumes per-slot optimality or a bounded gap.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the Lyapunov drift-plus-penalty framework used to convert the time-coupled problem into per-slot decisions and to derive the $C_{\\mathrm{opt}} + B/V$ bound in Theorem 9."},{"cited_title":"The application of parametric optimization and imbedding to the foundation and realization of a generalized primal decomposition approach,","cited_arxiv_id":null,"evidence_quote":"Tammer decomposition is cited as the mechanism that decouples the per-slot problem into communication-resource-allocation and task-offloading subproblems while preserving optimality."},{"cited_title":"Depen- dent rounding and its applications to approximation algorithms,","cited_arxiv_id":null,"evidence_quote":"Dependent rounding is the technique used to convert the fractional cloud-offloading solution into a binary one while preserving the total data volume sent to the cloud."},{"cited_title":"Task-based network reconfiguration in distributed UAV swarms: A bilateral matching approach,","cited_arxiv_id":null,"evidence_quote":"Bilateral matching is the basis of Algorithm 1, which determines which user associates with which server, local or MEC, in the energy-minimization stage."},{"cited_title":"A simple proof of: L = λW,","cited_arxiv_id":null,"evidence_quote":"Little's law is the standard result used to convert average queue lengths into the long-term queuing-delay constraints in Eqs. (12) and (13)."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Convex optimization theory is used to prove convexity of the bandwidth-allocation subproblem and to justify the closed-form solution in Theorem 3."},{"cited_title":"Computation peer offloading for energy-constrained mobile edge computing in small-cell net- works,","cited_arxiv_id":null,"evidence_quote":"Provides the single-slot-constraint (SSC) baseline that OJCTA is compared against in the energy and delay simulations."},{"cited_title":"Multi- timescale multi-dimension resource allocation for NOMA-edge computing-based power IoT with massive connectivity,","cited_arxiv_id":null,"evidence_quote":"Provides the no-cloud-collaboration (NCC) baseline used to demonstrate the value of the edge-cloud collaborative architecture."},{"cited_title":"QoE aware and cell capacity enhanced computation offloading for multi-server mobile edge computing systems with energy harvesting devices,","cited_arxiv_id":null,"evidence_quote":"Provides the genetic-algorithm-based joint task offloading and resource allocation baseline (GJTORA) used in the simulation comparisons."}],"review_version":1}