{"id":"7c633288-7c46-415b-b9f7-66a5ef6ea9f7","arxiv_id":"1908.04824","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":4.0,"correctness_risk":"low","formal_verification":"none","parameter_count":5,"one_line_summary":"A cost-minimizing ILP for joint service placement and task scheduling with QoS deadlines on a three-tier edge-cloud platform, plus two heuristics that approach optimal in simulations.","lead":"This paper formulates the problem of placing services and scheduling tasks on edge-cloud systems as an integer linear program that minimizes provider cost while meeting every user's deadline. It proves the problem is NP-hard and presents two greedy heuristics, finding in simulations that a global heuristic often comes close to the optimal solution.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Global heuristic Algorithm 2 as printed cannot implement the text's 'highest profit' rule: it inspects only the first unscheduled task's service and never divides profit by placement cost.","rationale":"The ILP formulation and NP-hardness reduction appear sound: setting placement costs to zero and capacities/deadlines to infinity recovers the general assignment problem, so that part of the paper is not the weak point. The reader's weakest-assumption (static, deterministic task arrivals) is real but explicitly listed as future work in the conclusion, so it does not undermine the internal claim; it only limits external applicability. My concern is more direct: the global heuristic, which is the paper's main algorithmic contribution, is not uniquely specified. The prose and the pseudocode disagree on two load-bearing details, namely whether all services are compared in each greedy decision and whether placement cost is part of the profit metric. Since the near-optimality evidence comes entirely from simulations of this heuristic, an ambiguous algorithm makes the headline claim unverifiable without the code. The proposed concrete test would settle the discrepancy by comparing both interpretations against the published figures and against the optimal ILP. The conditionality of the reader's verdict is therefore preserved, but the condition should explicitly include resolving the Algorithm 2 specification and releasing the simulation code.","tokens_in":7282,"tokens_out":8357,"duration_ms":88147,"concrete_test":"Obtain or reconstruct the authors' Python/Gurobi scripts and implement Algorithm 2 twice on the paper's Table II scenarios: (A) literally as printed, with s = service(first unscheduled t), profit = count of serviceable tasks, and no division by placement cost; (B) as described in the Section V.D prose, evaluating every service on every cloudlet with profit = count / P^p_mj and choosing the maximum. Run the same 20 Monte-Carlo scenarios used in Figures 4-6 and compute per-scenario optimality gaps. If variant A does not reproduce the published curves or has a mean gap clearly above 5% while variant B does, then the near-optimality claim belongs to the prose description rather than to the printed Algorithm 2.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim is that the global heuristic in Algorithm 2 performs close to optimal. The prose in Section V.D says the algorithm weighs every service on every computational device, divides the number of serviceable tasks by the placement cost, and then chooses the service/device pair with the highest profit. The pseudocode does not do this. In Algorithm 2, each while-loop iteration starts with s = service(t), where t is the first unscheduled task, so only tasks of that single service are used in the profit calculation; no comparison across services is made. The profit variable is also only a count of serviceable tasks, with no division by the placement cost P^p_mj, so the placement-cost term in the objective is entirely absent from the greedy selection. If the implemented code follows the pseudocode, the near-optimality shown in Figures 4-6 is for a different, weaker heuristic than the one described; if it follows the prose, the pseudocode is missing the essential branching and the cost normalization. No code or data is released, so a reader cannot tell which variant produced the reported results. The static-workload assumption flagged by the reader is acknowledged in the conclusion as future work and is a scope limitation rather than an internal discrepancy; the ambiguity of Algorithm 2 directly affects the reproducibility and attribution of the headline claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the joint problem of service placement and task scheduling in a three-tier edge-cloud platform, where each user task has a QoS deadline and the service provider minimizes placement and serving costs. The problem is formulated as an ILP (Eqs. 1-7), argued to be NP-hard via a reduction sketch to the general assignment problem, and solved approximately by two greedy heuristics: a local per-cloudlet algorithm and a global algorithm. Monte-Carlo simulations compare both heuristics against the Gurobi optimal solution while varying the number of users, the QoS factor, and the cost ratio beta. The paper claims that the global heuristic performs close to optimal with reduced complexity. The static, all-at-once workload model is acknowledged in the conclusion as a limitation and future work.","tokens_in":7539,"tokens_out":6861,"duration_ms":73281,"significance":"The problem is practically relevant, and the ILP formulation is clear and natural. The comparison between QoS-aware and QoS-less systems provides a useful sanity check, and the idea of comparing local versus global greedy decision making is reasonable. If the algorithmic description is made consistent and the empirical claims are properly supported with variability measures, the paper would be a useful contribution to edge-cloud service placement and task scheduling. At present, however, the central contribution is weakened by a major mismatch between the prose and pseudocode for the global heuristic, and by the lack of statistical evidence in the figures.","major_comments":[{"comment":"The pseudocode of Algorithm 2 does not implement the 'highest profit' rule described in the text. In each while-loop iteration the algorithm sets s = service(t) for the first unscheduled task t, so only tasks of that single service are considered; the prose explicitly says that the algorithm considers every service on every computational device and chooses the service/device pair with the highest profit. In addition, the profit variable in the pseudocode is only a count of serviceable tasks and is never divided by the placement cost P^p_mj, so the placement-cost term of the objective function is absent from the greedy choice. Algorithm 1 has a related discrepancy: the prose says 'schedule all tasks that can be scheduled' after choosing a service, but the pseudocode schedules only the single task t1 with the tightest QoS constraint in each iteration. Because no code or data is released, the reader cannot determine whether the near-optimal results in Figures 4-6 are produced by the described heuristic or by a weaker variant. Please reconcile the prose and pseudocode, or provide the implemented code.","section":"V.D, Algorithms 1 and 2"},{"comment":"The NP-hardness argument is a sketch rather than a formal reduction. To establish NP-hardness, the authors should give an explicit polynomial-time mapping from instances of the general assignment problem to instances of their ILP and prove that optimal solutions correspond. In particular, the statement that Eq. 7 is 'non-conflicting' because X can always be set to one should be replaced with a concrete construction (e.g., zero placement costs and all X variables set to one) that preserves the objective value of the general assignment problem. As written, the generalization argument is plausible but not a complete proof.","section":"V.B, NP-Hardness"},{"comment":"The simulations use twenty Monte-Carlo scenarios per configuration, but Figures 4-6 show only point estimates or line plots without error bars, confidence intervals, or any statistical test. The paper's headline claim that the global heuristic is 'close to optimal' is therefore not quantitatively supported: the observed gaps could be small on average but large in individual instances, and the visual closeness cannot be assessed without a measure of variability. Please add error bars or confidence intervals and state the distribution of the optimality gap across the scenarios.","section":"V.E and Figures 4-6"}],"minor_comments":[{"comment":"The phrase 'in a Edge to Cloud Platform' should be corrected to 'in an Edge-to-Cloud Platform'; similar grammar issues appear in the abstract.","section":"Title and Abstract"},{"comment":"In Eq. (5), d_J(t)j is described as a distance measured in ping time while tIn and tOut are packet sizes, so the product d_J(t)j * tIn has inconsistent units. Please define the distance and packet quantities so that completion time is derived consistently.","section":"Eq. (5)"},{"comment":"Please specify the exact random distributions used to generate cloudlet locations, service-task mappings, and cost parameters. The table lists ranges but not the generation procedure, which is needed for reproducibility.","section":"V.E, Simulation Parameters"},{"comment":"The table lists |M| = 1000 service types while |T| is at most 500; please clarify how service types are assigned to tasks and whether the setting allows each task to have a unique service type.","section":"Table II"},{"comment":"Adding error bars would also help readers see the overlap between the global heuristic and the optimal solution; consider using markers and a legend that make the three curves distinguishable in grayscale.","section":"Figures 4-6"},{"comment":"The static 'arrives all at once' assumption is acknowledged in the conclusion, but the model section should state explicitly that online arrivals and execution-time uncertainty are out of scope, so that the claims of near-optimality are properly qualified.","section":"Conclusion and Model Scope"}],"recommendation":"major_revision","confidential_remarks":"The central uncertainty is whether the implemented global heuristic matches the prose or the pseudocode; without a code release, the reader cannot verify the reported results. If the authors can provide the executable code or a clearly corrected algorithm and add statistical measures to the figures, the paper would be ready for reconsideration."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a solid, narrow edge-to-cloud service placement and task scheduling paper. The ILP formulation is coherent and the cost-aware QoS framing is sensible. But the headline result—the global heuristic is near-optimal—rests on an algorithm that is described one way in the prose and another way in the pseudocode. That discrepancy is material and has to be fixed before the central claim can be trusted.\n\nWhat is new: the paper extends the authors' earlier joint placement/scheduling work by explicitly adding provider cost (placement plus serving) to the objective, alongside QoS deadlines. The constraints are internally consistent, and the NP-hardness sketch via reduction from the general assignment problem is standard but correct. The two greedy heuristics are simple and honestly compared against exact Gurobi solutions over multiple Monte-Carlo runs. The static-workload assumption is acknowledged in the conclusion as a future direction, which is fair.\n\nThe stress-test concern is real. The text in Section V.D says the global heuristic considers every service/device pair, divides the number of serviceable tasks by the placement cost, and picks the pair with the highest profit. The pseudocode in Algorithm 2 does something weaker: it fixes s to the service of the first unscheduled task, so only one service class is ever considered per iteration, and the profit is a raw count of serviceable tasks with no division by the placement cost. As printed, the code cannot implement the described rule. Since no code or data is released, a reader cannot tell which variant produced Figures 4–6. That ambiguity is load-bearing for the near-optimality claim.\n\nOther soft spots are moderate. The Monte-Carlo figures have no error bars or confidence intervals, no statistical tests are reported, and there is no comparison against existing QoS-aware placement heuristics. The NP-hardness proof is sketched rather than fully formalized. None of these by themselves sink the paper, but combined with the Algorithm 2 issue, they mean the evidence for the central claim is incomplete.\n\nWho benefits: readers working on edge-cloud service placement who want a compact ILP baseline and a simple local-vs-global heuristic contrast. With the algorithm corrected, the pseudocode aligned to the prose, and code or at least detailed simulation data released, this would be a useful benchmark paper. As it stands, it deserves a serious referee—this should not be desk-rejected—but I would send it back for major revision, specifically to resolve the heuristic description and to strengthen the simulation reporting. I would not cite it in its current form.","headline":"The ILP model is a reasonable within-subfield contribution, but the global heuristic's prose description and pseudocode disagree in a way that undermines the near-optimality claim until corrected.","tokens_in":8014,"tokens_out":2405,"would_cite":false,"duration_ms":26644,"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":"A global greedy heuristic can place edge-cloud services and schedule user tasks at near-optimal cost while meeting every user's deadline.","keywords":["service placement","task scheduling","edge-to-cloud platform","quality of service","integer linear programming","NP-hardness","greedy heuristic","cost optimization"],"falsifier":"Under the paper's own parameters (four cloudlets, hundreds of services, 300–500 tasks, QoS factor 2.5 to 5), run the global greedy and the ILP optimum on every Monte-Carlo replication and record the cost ratio; if any tested scenario has the greedy cost more than ten percent above optimal, or leaves any user's deadline unmet while the ILP meets it, the paper's 'close to optimal' claim fails within its stated regime. A complementary adversarial search over tiny instances (four cloudlets, a handful of tasks) would establish whether the greedy-to-optimal gap is bounded or can grow without limit.","tokens_in":7097,"feed_emoji":"☁️","tokens_out":13016,"duration_ms":126043,"temperature":0.7,"pith_summary":"The paper sets out to show that a service provider can jointly choose where to place software services on edge cloudlets and which computational device should handle each user's task, so that every request meets its deadline while the provider's total cost is minimized. It casts that joint decision as an integer linear program and proves the problem is NP-hard by reducing the general assignment problem to it. The paper then proposes two greedy heuristics: one that fills each cloudlet with its own users' tightest-deadline tasks, and one that picks service/device pairs globally by the number of deadline-feasible tasks they can serve per unit of placement cost. The main empirical claim is that the global greedy heuristic lands close to the optimal ILP cost across the tested ranges of user count, QoS strictness, and cloudlet-versus-cloud pricing, while running far more cheaply. If that holds, providers can meet hard latency requirements in applications such as augmented reality and real-time video analysis without solving an exponentially hard optimization from scratch each time.","feed_headline":"Greedy placement nears optimal edge-cloud QoS at low cost","feed_subtitle":"A global view of which services go where meets all user deadlines at near-optimal provider cost, simulations show.","key_machinery":"The argument is carried by an ILP over two binary decision families: $X_{mj}$, whether service $m$ is placed on cloudlet $j$, and $Y_{tj}$, whether task $t$ is scheduled on device $j$. The objective sums placement costs $P^p_{mj}X_{mj}$ and serving costs $P^s_{M(t)j}Y_{tj}$; constraints enforce storage and processing limits per cloudlet, assign each task to exactly one device, force the completion time $\\delta(t,j)=d_{J(t),j}\\,t_{\\mathrm{in}}+\\sigma(t)+d_{J(t),j}\\,t_{\\mathrm{out}}$ below the QoS threshold $Q_t$, and allow scheduling only where the needed service is placed ($Y_{tj}\\le X_{M(t)j}$). NP-hardness is shown by zeroing placement costs and making storage and deadlines infinite, which recovers the general assignment problem. The global heuristic's operative score is the profit of a service/device pair: the number of tasks of that service type that can still meet their deadlines on that device, divided by the placement cost, and the algorithm repeatedly commits to the highest-profit pair until every task is scheduled.","core_discovery":"On the paper's own terms, the central claim is that joint service placement and task scheduling in a three-tier edge-to-cloud platform—users, cloudlets, and remote cloud—admits a single ILP formulation whose objective is to minimize placement plus serving cost while satisfying per-task deadline, storage, and processing constraints, and that this problem is NP-hard. The companion algorithmic claim is that a global greedy rule, which repeatedly commits to the service/cloudlet combination with the highest ratio of deadline-feasible tasks served to placement cost, performs close to the ILP optimum in simulation and clearly outperforms a local greedy that packs each cloudlet with its own users' tightest-deadline services first. The paper also claims that QoS awareness is affordable: a QoS-less scheduler drops more than thirty percent of tasks in the simulated settings, while the QoS-aware version drops none, at only a modest increase in provider cost.","pith_inferences":["Beyond the paper's static model, the near-optimality claim has not been tested for streaming workloads; re-running the global heuristic on batches of arriving tasks and comparing cost and deadline-miss rate against a reoptimizing baseline would show whether the result survives dynamic arrivals.","The NP-hardness reduction implies no polynomial algorithm can guarantee optimality unless P=NP, so the practically relevant open question is the heuristic's worst-case approximation ratio, which could be probed by searching small adversarial instances.","The profit score used by the global heuristic is a natural component to reuse for decisions the paper does not model, such as migrating a service between cloudlets or placing a popular service on several cloudlets at once."],"forward_implications":["The global greedy offers a practical way to meet all user deadlines at near-optimal provider cost without solving an ILP, so deployments where the optimum is computationally out of reach can still approach it.","Cloudlets that consider remote requests, not just their locally connected users, achieve lower provider cost, which supports the paper's recommendation for system-wide awareness in edge-cloud management.","As the QoS deadline becomes looser, the global heuristic's cost converges to the optimum because both it and the optimum shift more tasks to the inexpensive cloud, whereas the local heuristic cannot exploit that slack.","The QoS-aware formulation eliminates dropped tasks for only a modest cost increase, so enforcing user deadlines is presented as a worthwhile trade for the service provider."],"supporting_citations":[{"why":"Supplies the prior joint placement/scheduling formulation in edge clouds and the NP-hardness proof that this paper builds on and re-targets at provider cost.","marker":"[2]"},{"why":"Provides the more general placement/scheduling algorithm from the authors' earlier work, which maximized users served rather than minimizing cost and meeting all QoS.","marker":"[4]"},{"why":"Gives a cloudlet service-allocation/scheduling approach that ignores heterogeneous cloudlet limits, motivating this paper's hardware-constraint-aware model.","marker":"[6]"},{"why":"Presents an ILP-based QoS-aware fog placement and scheduling optimization that this paper extends by adding service placement prior to scheduling.","marker":"[7]"},{"why":"Supplies a QoS-based task distribution method that maximizes handled tasks but ignores provider cost, the baseline the paper argues is incomplete.","marker":"[8]"},{"why":"Provides the closest competing QoS-aware placement/scheduling algorithm, which optimizes provider cost but not jointly with user QoS, defining the comparison the global heuristic must improve on.","marker":"[10]"}],"fun_headline_variants":["Global greedy beats local for edge-cloud QoS placement","Near-optimal edge-cloud scheduling via global greedy","QoS-aware greedy places services, hits every deadline","Edge-cloud cost minimized with global greedy placement","Global greedy heuristic nears optimal in edge-cloud"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that every task is known in advance and arrives at the same time, with deterministic execution and communication times; if requests arrive dynamically or runtimes vary, the ILP and both heuristics no longer directly apply, so the near-optimality result would not automatically transfer.","fun_headline_variants_meta":{"raw":{"variants":["Global greedy beats local for edge-cloud QoS placement","Near-optimal edge-cloud scheduling via global greedy","QoS-aware greedy places services, hits every deadline","Edge-cloud cost minimized with global greedy placement","Global greedy heuristic nears optimal in edge-cloud"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000345,"raw_usage":{"total_tokens":1869,"prompt_tokens":897,"completion_tokens":972,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":513,"completion_tokens_details":{"reasoning_tokens":901}},"tokens_in":513,"tokens_out":972,"duration_ms":9510,"temperature":1.0,"reasoning_tokens":901,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:31:31.684181+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Under the paper's own parameters (four cloudlets, hundreds of services, 300–500 tasks, QoS factor 2.5 to 5), run the global greedy and the ILP optimum on every Monte-Carlo replication and record the cost ratio; if any tested scenario has the greedy cost more than ten percent above optimal, or leaves any user's deadline unmet while the ILP meets it, the paper's 'close to optimal' claim fails within its stated regime. A complementary adversarial search over tiny instances (four cloudlets, a handful of tasks) would establish whether the greedy-to-optimal gap is bounded or can grow without limit.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the prior joint placement/scheduling formulation in edge clouds and the NP-hardness proof that this paper builds on and re-targets at provider cost."},{"cited_title":"Edge-centric computing: Vision and challenges","cited_arxiv_id":null,"evidence_quote":"Provides the more general placement/scheduling algorithm from the authors' earlier work, which maximized users served rather than minimizing cost and meeting all QoS."},{"cited_title":"Ksentini , T","cited_arxiv_id":null,"evidence_quote":"Gives a cloudlet service-allocation/scheduling approach that ignores heterogeneous cloudlet limits, motivating this paper's hardware-constraint-aware model."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Presents an ILP-based QoS-aware fog placement and scheduling optimization that this paper extends by adding service placement prior to scheduling."},{"cited_title":"Towards qos-aware fog service placement","cited_arxiv_id":null,"evidence_quote":"Supplies a QoS-based task distribution method that maximizes handled tasks but ignores provider cost, the baseline the paper argues is incomplete."},{"cited_title":"Dynamic Service Migration in Mobile Edge Computing Based on Markov Decision Process","cited_arxiv_id":"1506.05261","evidence_quote":"Provides the closest competing QoS-aware placement/scheduling algorithm, which optimizes provider cost but not jointly with user QoS, defining the comparison the global heuristic must improve on."}],"review_version":1}