Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

Algorithmics and Complexity of Cost-Driven Task Offloading with Submodular Optimization in Edge-Cloud Environments

T0 review · 3 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper claims that edge-cloud task offloading is NP-hard without its communication assumption but becomes polynomially solvable, even with latency constraints, when the assumption holds.

desk verdict The NP-hardness reduction is solid and new; the central submodularity theorem is false as stated, so the main polynomial-time claim collapses. read the letter →

arxiv 2411.15687 v1 pith:4KBRXMB3 submitted 2024-11-24 cs.DM cs.CCcs.DC

Longkun Guo , Jiawei Lin , Xuanming Xu , Peng Li This is my paper · ORCID
classification cs.DMcs.CCcs.DC MSC 68Q1790C27
keywords taskoffloadingedge-cloudcomputingsubmodularminimizationNP-hardnesscommunicationassumptionlatencyconstraintMAX-CUTreductioncostoptimization
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper studies the task offloading problem, in which each computing task is assigned to either an edge server or a cloud server and the total computation plus communication cost is minimized. Its central claim is a dichotomy: without a 'communication assumption' the problem is NP-hard, even in the symmetric case, while with the assumption the cost function is submodular and the problem is solvable in strongly polynomial time. The assumption states that communicating between two cloud servers is no more expensive than communication crossing the edge–cloud boundary or communication between edge servers. Because submodular minimization has polynomial algorithms, the paper turns a hardness result into a tractability result under a plausible real-world cost ordering. A sympathetic reader would care because the same assumption that makes the model realistic is the one that makes optimal offloading computationally feasible.

What carries the argument

The central object is the cost-increment function $F(X)=\Gamma(X)-\Gamma(\emptyset)$, which measures how the total service cost changes when the task set $X$ is executed on the cloud instead of all tasks being executed on the edge. The paper proves submodularity by expanding the difference $(F(A\cup\{v_m\})-F(A))-(F(B\cup\{v_m\})-F(B))$ into a sum over tasks $j\in B\setminus A$ of paired terms; the communication assumption makes each paired term nonnegative, because an edge that becomes intra-cloud instead of inter-partition cannot increase in cost. This pairwise nonnegativity is what carries the argument, and it is what permits the problem to be handed to existing strongly polynomial submodular-minimization algorithms.

What would settle it

Construct a small instance with four tasks satisfying Definition 1 but with $l^1_{ij}$ much larger than $l^2_{ij}$ and $l^3_{ij}$ (for example $l^1=10$, $l^2=l^3=1$, $l^4=0$), then exhaustively check all partitions to see whether $F(A\cup\{v_m\})-F(A)\ge F(B\cup\{v_m\})-F(B)$ holds for all $A\subseteq B$ and $v_m\notin B$; a single violation would refute Theorem 7 as stated.

Watch

Extended reading notes

Core claim

The paper's main discovery is Theorem 7: for the latency-constrained offloading problem, the cost-increment function $F(X)=C_{\mathrm{total}}(V\setminus X,X)-C_{\mathrm{total}}(V,\emptyset)$ is submodular whenever the communication assumption $l^4_{ij}\le l^2_{ij},l^3_{ij}$ holds for every edge. Submodularity means the marginal cost of moving a task to the cloud decreases as the set of cloud-assigned tasks grows, which is exactly the diminishing-returns behavior needed for polynomial minimization. With this in hand, Offloading-CommA and Offloading-LCCA can be solved optimally in strongly polynomial time by minimizing $F$ over all $X\subseteq V\setminus T$. Complementing this, the paper proves that without the assumption the offloading problem is NP-hard even when computation costs are zero and communication costs are symmetric, via a reduction from MAX-CUT. Taken together, the paper argues that the communication assumption is the dividing line that separates polynomial solvability from NP-hardness.

Load-bearing premise

The whole polynomial-time result depends on a cost-ordering condition that the paper never states: the proof needs the edge-cost savings from moving a task to the cloud to be nonnegative in both directions, which fails when communication between two edge servers is much more expensive than communication across the edge–cloud boundary.

Editorial extensions

If this is right

  • Under the communication assumption, Offloading-CommA is solvable optimally in strongly polynomial time.
  • The latency-constrained version Offloading-LCCA remains polynomially solvable when some tasks must stay on edge servers.
  • Without the assumption, the offloading problem is NP-hard even with zero computation costs and symmetric communication costs.
  • The communication assumption, not symmetry or computation costs, is the key factor separating NP-hardness from polynomial solvability in this model.
  • Experiments on real-world and synthetic graphs show the submodular-minimization algorithm matches the ILP optimum and runs faster than the previous HETO heuristic.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the missing pairwise ordering is genuinely required, the true picture may be finer than a simple dichotomy: instances satisfying the full pairwise ordering are polynomial, while instances satisfying only the stated assumption may still be hard, and a cleaner sufficient condition would be $l^1_{ij}+l^4_{ij}\le l^2_{ij}+l^3_{ij}$ for every edge.
  • The same cost-increment trick could be applied to other two-sided assignment problems with asymmetric communication costs, as long as a pairwise ordering makes every marginal difference nonnegative.
  • A testable engineering consequence is that exact optimal offloading is feasible when intra-cloud bandwidth is cheap but edge-to-cloud links are slow, whereas systems with cheap edge-to-edge links may still need heuristics.
  • If the missing condition is added to the model, the dichotomy result would become a practical diagnostic: check the four communication costs on each link, and the complexity class is decided by a simple inequality.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies the cost-driven task offloading problem in edge-cloud environments, where each task is assigned to either an edge or a cloud server and the total cost combines computation and communication costs. It introduces a 'communication assumption' (Definition 1) requiring intra-cloud communication costs l4_ij to be no larger than inter-partition costs l2_ij and l3_ij. The paper claims two main results: (i) the symmetric offloading problem is NP-hard via a reduction from MAX-CUT (Theorem 2), and (ii) under the communication assumption, the cost-increment function F(X) = C_total(V\X, X) − C_total(V, ∅) is submodular (Theorem 7), so the offloading problem and its latency-constrained variant are polynomially solvable by submodular function minimization (Corollary 8). The paper also reports experiments comparing the proposed submodular-minimization algorithm (SMA) with an ILP baseline and a prior heuristic (HETO).

Significance. The NP-hardness reduction of Section III appears sound and, if correct, closes the open question stated in [15] about the symmetric case, which is a worthwhile contribution. The experimental methodology is also a strength: the paper validates its algorithm against an independent ILP solver and reports running times on SNAP and synthetic datasets. However, the central algorithmic claim is Theorem 7, and that claim is false under the stated assumptions; the proof requires an additional condition that is neither part of Definition 1 nor stated anywhere. Since Corollary 8 and the polynomial-solvability dichotomy depend on Theorem 7, the paper's main positive result collapses. The experiments, while extensive, do not repair the missing proof and in fact include an 'adhering' cost ratio that violates the unstated condition needed by the proof.

major comments (3)
  1. [Section IV.B, Theorem 7 and Eq. (18)] The proof of Theorem 7 asserts that the second term of Eq. (18) is nonnegative, but that term equals l2_{m,j} − l1_{m,j} (or, in the two-sided version, l2_{m,j} + l3_{m,j} − l1_{m,j} − l4_{m,j}) for j ∈ B\A, and Definition 1 imposes no relation between l1 and l2. A concrete counterexample satisfies every stated assumption: two tasks with a single directed edge (v_m, v_j), zero computation costs, and (l1, l2, l3, l4) = (100, 1, 1, 0). For this instance Definition 1 holds (0 ≤ 1 and 0 ≤ 1), but F({v_m}) − F(∅) = −99 while F({v_m, v_j}) − F({v_j}) = −1, so the diminishing-returns inequality of Definition 6 fails. Theorem 7 is therefore false as stated, and Corollary 8 is unsupported.
  2. [Section IV.B, Eq. (16)] The displayed formula for F(A∪{v_m}) − F(A) is incorrect in two respects. First, the computation-cost difference should be wcld_m − wedg_m, the negative of the expression shown, since moving v_m from the edge to the cloud changes the computation cost by that amount. Second, the communication sums include only edges of the form (v_m, v_j) and omit edges (v_j, v_m) entering v_m; those edges also change classification when v_m moves, contributing additional terms that are not constrained by Definition 1. Correcting these errors introduces exactly the l2 ≥ l1 type of condition whose absence breaks Theorem 7.
  3. [Section V.B.3 and Fig. 7] The experimental validation does not isolate the assumption used in the proof of Theorem 7. The 'adhering' ratio (8:6:7:5) satisfies Definition 1 but violates the unstated condition l2 ≥ l1 (since 8 > 6), so the reported optimality of SMA on that ratio cannot be explained by the theorem as proven. More generally, all of the 'violating' ratios violate l2 ≥ l1 as well as Definition 1, so the experiments cannot discriminate between the paper's stated assumption and the stronger condition actually needed for submodularity. The empirical agreement with ILP is therefore not evidence for the theorem.
minor comments (4)
  1. [Section II, after Eq. (2)] The sentence 'For briefness, we call l1_ij and l4_ij as intra-edge and intra-cloud costs, respectively, and call l1_ij and l4_ij as inter-partition cost' should read 'l2_ij and l3_ij' in the second mention; otherwise it misidentifies which costs are inter-partition.
  2. [Section V.B.2] The sentence 'This trend is attributed to the HETO’s exponential growth in runtime, which aligns with its time complexity of O(E²)' is internally inconsistent: O(E²) is polynomial, not exponential.
  3. [Section IV.C.2, Fig. 3 description] The text says 'red edges turn out to be intra-cloud communication' when describing a solution whose red nodes are executed at the edge; those edges should be called intra-edge communication.
  4. [Section III, Lemma 3 proof] The first paragraph of the proof states that C′ ≤ C 'apparently holds' because the offloading solution is feasible, but feasibility alone does not imply a cost bound; the argument should instead assume that a solution of cost at most C exists. Both directions of the reduction are present, but the logical structure of the lemma proof is confusing.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivation is self-contained, and the proof gap in Theorem 7 is an unstated assumption rather than a circular reduction.

full rationale

The paper does not fit parameters and then rename them as predictions; the cost function F(X) is explicitly defined from the model's total cost, and the submodularity claim is a mathematical property to be proved, not assumed or imported from self-citation. The communication assumption is an explicit modeling postulate, not a consequence of the result. The algorithm's behavior is checked against an independent ILP benchmark, and the cited submodular-minimization algorithms and the MAX-CUT reduction are external results. The main weakness in Theorem 7 is that its proof asserts that the second term in Eq. (18) is nonnegative without the required condition l2 >= l1 (or a suitable four-cost ordering); this is a correctness gap or an unstated assumption, not an instance of circular reasoning, because the claim does not reduce to its inputs by definition and no fitted parameter or self-citation is used to force the conclusion.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces no new physical entities. Its main result rests on the communication assumption and an unstated extra cost ordering that the proof silently uses; the latter is not justified and is falsified by simple two-task instances.

assumptions (4)
  • standard math MAX-CUT is NP-hard
    Used in the reduction in Section III, Theorem 2.
  • standard math Strongly polynomial algorithms exist for submodular function minimization (Iwata et al.)
    Used in Section IV.B to claim polynomial solvability from Theorem 7.
  • domain assumption Communication assumption: l4_ij <= l2_ij and l4_ij <= l3_ij for all edges
    Definition 1; motivated by cloud-internal links being cheaper than cross links. This is the key modeling premise and is not universally true.
  • ad hoc to paper Unstated pairwise condition l1_ij <= l2_ij (or l1_ij + l4_ij <= l2_ij + l3_ij) needed for submodularity
    Theorem 7 proof, Eq (18) second term, requires this but it is not part of Definition 1; with l1 large, F is not submodular.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Algorithmics and Complexity of Cost-Driven Task Offloading with Submodular Optimization in Edge-Cloud Environments." pith.science (2026). https://pith.science/paper/4KBRXMB3

@misc{pith2026241115687,
  author       = {Pith},
  title        = {Pith review of: Algorithmics and Complexity of Cost-Driven Task Offloading with Submodular Optimization in Edge-Cloud Environments},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4KBRXMB3}},
  note         = {Machine review of arXiv:2411.15687}
}
read the original abstract

Emerging applications such as autonomous driving pose the challenge of efficient cost-driven offloading in edge-cloud environments. This involves assigning tasks to edge and cloud servers for separate execution, with the goal of minimizing the total service cost including communication and computation costs. In this paper, observing that the intra-cloud communication costs are relatively low and can often be neglected in many real-world applications, we consequently introduce the so-called communication assumption which posits that the intra-cloud communication costs are not higher than the inter-partition communication cost between cloud and edge servers, nor the cost among edge servers. As a preliminary analysis, we first prove that the offloading problem without the communication assumption is NP-hard, using a reduction from MAX-CUT. Then, we show that the offloading problem can be modeled as a submodular minimization problem, making it polynomially solvable. Moreover, this polynomial solvability remains even when additional constraints are imposed, such as when certain tasks must be executed on edge servers due to latency constraints. By combining both algorithmics and computational complexity results, we demonstrate that the difficulty of the offloading problem largely depends on whether the communication assumption is satisfied. Lastly, extensive experiments are conducted to evaluate the practical performance of the proposed algorithm, demonstrating its significant advantages over the state-of-the-art methods in terms of efficiency and cost-effectiveness.

Figures

Figures reproduced from arXiv: 2411.15687 by the authors.

Figure 1
Figure 1. A typical configuration of the edge-cloud environment. [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. An instance of Offloading-LCCA with a solution In the above formulation, for the first term of the second line, when Vcld = A ∪ {vm}, we have j /∈ I (Vedg) since j ∈ I (B \ A), and hence m and j are in different partitions. So l(vm, vj ) is inter-partition communication cost in the case. In contrast, when Vcld = B ∪ {vm}, m and j are in the same partition and hence l(vm, vj ) is intra-cloud communication cost. Follo… view at source ↗
Figure 3
Figure 3. An instance of Offloading-CommA with outputs of the algorithms based on submodular minimization and Min-Cut instance could be with four different communication costs, and hence can not transform to the graph in which the Min￾Cut algorithm can correctly work. As shown in Fig. 3c, the values of the blue edges can not be determined according to the transformation as in the algorithm based on Min-Cut [15]. V. NUMERICAL … view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: Offloading results on the different datasets. [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]
Figure 5
Figure 5. Figure 5: Offloading results over graph datasets of different sizes. [PITH_FULL_IMAGE:figures/full_fig_p009_5.png]
Figure 6
Figure 6. Figure 6: The influence of communication cost on the performance of algorithms. [PITH_FULL_IMAGE:figures/full_fig_p010_6.png]
Figure 7
Figure 7. Figure 7: Comparison of offloading results without communication assumption. [PITH_FULL_IMAGE:figures/full_fig_p011_7.png]
Figure 8
Figure 8. Figure 8: Offloading results comparison over the graph of different densities. [PITH_FULL_IMAGE:figures/full_fig_p011_8.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Collaborative Inference and Learning between Edge SLMs and Cloud LLMs: A Survey of Algorithms, Execution, and Open Challenges

    cs.DC 2025-07 conditional novelty 4.0 of 10

    A survey that builds a taxonomy of edge-cloud LLM-SLM collaboration for inference and training, claiming to be the first to unify both phases.

Reference graph

Works this paper leans on

44 extracted references · 38 canonical work pages · cited by 1 Pith paper

  1. [15]

    Algorithmics of cost-driven com- putation offloading in the edge-cloud environment,

    M. Du, Y . Wang, K. Ye, and C. Xu, “Algorithmics of cost-driven com- putation offloading in the edge-cloud environment,” IEEE Transactions on Computers, vol. 69, no. 10, pp. 1519–1532, 2020

    work page 2020

  2. [1]

    Edge computing: Vision and challenges,

    W. Shi, J. Cao, Q. Zhang, Y . Li, and L. Xu, “Edge computing: Vision and challenges,” IEEE internet of things journal , vol. 3, no. 5, pp. 637–646, 2016

    2016

  3. [2]

    Edge computing security: State of the art and challenges,

    Y . Xiao, Y . Jia, C. Liu, X. Cheng, J. Yu, and W. Lv, “Edge computing security: State of the art and challenges,” Proceedings of the IEEE , vol. 107, no. 8, pp. 1608–1631, 2019

    work page 2019

  4. [3]

    Edge computing for autonomous driving: Opportunities and challenges,

    S. Liu, L. Liu, J. Tang, B. Yu, Y . Wang, and W. Shi, “Edge computing for autonomous driving: Opportunities and challenges,” Proceedings of the IEEE, vol. 107, no. 8, pp. 1697–1716, 2019

    2019

  5. [4]

    A potential game theoretic approach to computation offloading strategy optimization in end-edge-cloud com- puting,

    Y . Ding, K. Li, C. Liu, and K. Li, “A potential game theoretic approach to computation offloading strategy optimization in end-edge-cloud com- puting,” IEEE Transactions on Parallel and Distributed Systems, vol. 33, no. 6, pp. 1503–1519, 2022

    work page 2022

  6. [5]

    Todg: Distributed task offloading with delay guarantees for edge computing,

    S. Yue, J. Ren, N. Qiao, Y . Zhang, H. Jiang, Y . Zhang, and Y . Yang, “Todg: Distributed task offloading with delay guarantees for edge computing,” IEEE Transactions on Parallel and Distributed Systems , vol. 33, no. 7, pp. 1650–1665, 2022

    work page 2022

  7. [6]

    A survey and taxonomy on task offloading for edge-cloud computing,

    B. Wang, C. Wang, W. Huang, Y . Song, and X. Qin, “A survey and taxonomy on task offloading for edge-cloud computing,” IEEE Access, vol. 8, pp. 186 080–186 101, 2020

    2020

  8. [7]

    Optimal joint scheduling and cloud offloading for mobile applications,

    S. E. Mahmoodi, R. N. Uma, and K. P. Subbalakshmi, “Optimal joint scheduling and cloud offloading for mobile applications,” IEEE Transactions on Cloud Computing , vol. 7, no. 2, pp. 301–313, 2019

    work page 2019

Show all 44 references
  1. [8]

    Energy-efficient decision making for mobile cloud offloading,

    H. Wu, Y . Sun, and K. Wolter, “Energy-efficient decision making for mobile cloud offloading,” IEEE Transactions on Cloud Computing , vol. 8, no. 2, pp. 570–584, 2020

    2020

  2. [9]

    Cloud computing for mobile users: Can offloading computation save energy?

    K. Kumar and Y .-H. Lu, “Cloud computing for mobile users: Can offloading computation save energy?” Computer, vol. 43, no. 4, pp. 51– 56, 2010

    2010

  3. [10]

    A survey of computation offloading for mobile systems,

    K. Kumar, J. Liu, Y .-H. Lu, and B. Bhargava, “A survey of computation offloading for mobile systems,” Mobile networks and Applications , vol. 18, no. 1, pp. 129–140, 2013

    2013

  4. [11]

    An optimal offloading partitioning algorithm in mobile cloud computing,

    H. Wu, W. Knottenbelt, K. Wolter, and Y . Sun, “An optimal offloading partitioning algorithm in mobile cloud computing,” in International Conference on Quantitative Evaluation of Systems . Springer, 2016, pp. 311–328

    2016

  5. [12]

    Computational offloading with delay and capac- ity constraints in mobile edge,

    W. Wang and W. Zhou, “Computational offloading with delay and capac- ity constraints in mobile edge,” in 2017 IEEE International Conference on Communications (ICC) . IEEE, 2017, pp. 1–6

    2017

  6. [13]

    On cost-driven collaborative data caching: A new model approach,

    Y . Wang, S. He, X. Fan, C. Xu, and X.-H. Sun, “On cost-driven collaborative data caching: A new model approach,” IEEE Transactions on Parallel and Distributed Systems , vol. 30, no. 3, pp. 662–676, 2018

    2018

  7. [14]

    Computation offloading for mobile- edge computing with maximum flow minimum cut,

    L. Dong, F. Wang, and J. Shan, “Computation offloading for mobile- edge computing with maximum flow minimum cut,” in Proceedings of the 2nd International Conference on Computer Science and Application Engineering, 2018, pp. 1–5

    2018

  8. [16]

    Approximation algorithm for the offloading problem in edge computing,

    X. Han, G. Gao, L. Ning, Y . Wang, and Y . Zhang, “Approximation algorithm for the offloading problem in edge computing,” in Interna- tional Conference on Wireless Algorithms, Systems, and Applications . Springer, 2020, pp. 134–144

    2020

  9. [17]

    Energy efficient task caching and offloading for mobile edge computing,

    Y . Hao, M. Chen, L. Hu, M. S. Hossain, and A. Ghoneim, “Energy efficient task caching and offloading for mobile edge computing,” IEEE Access, vol. 6, pp. 11 365–11 373, 2018

    2018

  10. [18]

    Dynamic computation offloading in edge computing for internet of things,

    Y . Chen, N. Zhang, Y . Zhang, and X. Chen, “Dynamic computation offloading in edge computing for internet of things,” IEEE Internet of Things Journal, vol. 6, no. 3, pp. 4242–4251, 2018

    2018

  11. [19]

    A load balancing algorithm for mobile devices in edge cloud computing environments,

    J. Lim and D. Lee, “A load balancing algorithm for mobile devices in edge cloud computing environments,” Electronics, vol. 9, no. 4, p. 686, 2020

    2020

  12. [20]

    Job scheduling to minimize total completion time on multiple edge servers,

    X. Fang, Z. Cai, W. Tang, G. Luo, L. Junzhou, R. Bi, and H. Gao, “Job scheduling to minimize total completion time on multiple edge servers,” IEEE Transactions on Network Science and Engineering , 2019

    2019

  13. [21]

    Online job dispatching and scheduling in edge-clouds,

    H. Tan, Z. Han, X.-Y . Li, and F. C. Lau, “Online job dispatching and scheduling in edge-clouds,” in IEEE INFOCOM 2017-IEEE Conference on Computer Communications . IEEE, 2017, pp. 1–9

    2017

  14. [22]

    Computa- tion off-loading in resource-constrained edge computing systems based on deep reinforcement learning,

    C. Luo, J. Zhang, X. Cheng, Y . Hong, Z. Chen, and X. Xing, “Computa- tion off-loading in resource-constrained edge computing systems based on deep reinforcement learning,” IEEE Transactions on Computers , vol. 73, no. 1, pp. 109–122, 2024

    2024

  15. [23]

    Dedas: Online task dispatching and scheduling with bandwidth constraint in edge computing,

    J. Meng, H. Tan, C. Xu, W. Cao, L. Liu, and B. Li, “Dedas: Online task dispatching and scheduling with bandwidth constraint in edge computing,” in IEEE INFOCOM 2019-IEEE Conference on Computer Communications. IEEE, 2019, pp. 2287–2295

    2019

  16. [24]

    Towards optimal application offloading in heterogeneous edge-cloud computing,

    T. Ji, X. Wan, X. Guan, A. Zhu, and F. Ye, “Towards optimal application offloading in heterogeneous edge-cloud computing,” IEEE Transactions on Computers, vol. 72, no. 11, pp. 3259–3272, 2023

    2023

  17. [25]

    Dependent task offloading for edge computing based on deep rein- forcement learning,

    J. Wang, J. Hu, G. Min, W. Zhan, A. Y . Zomaya, and N. Georgalas, “Dependent task offloading for edge computing based on deep rein- forcement learning,” IEEE Transactions on Computers , vol. 71, no. 10, pp. 2449–2461, 2022

    2022

  18. [26]

    Collaborative cloud-edge-end task offloading in mobile-edge computing networks with limited commu- nication capability,

    C. Kai, H. Zhou, Y . Yi, and W. Huang, “Collaborative cloud-edge-end task offloading in mobile-edge computing networks with limited commu- nication capability,” IEEE Transactions on Cognitive Communications and Networking, vol. 7, no. 2, pp. 624–634, 2021

    2021

  19. [27]

    Service placement with provable guarantees in heterogeneous edge computing systems,

    S. Pasteris, S. Wang, M. Herbster, and T. He, “Service placement with provable guarantees in heterogeneous edge computing systems,” in IEEE INFOCOM 2019-IEEE Conference on Computer Communications. IEEE, 2019, pp. 514–522

    2019

  20. [28]

    Winning at the starting line: Joint network selection and service placement for mobile edge computing,

    B. Gao, Z. Zhou, F. Liu, and F. Xu, “Winning at the starting line: Joint network selection and service placement for mobile edge computing,” in IEEE INFOCOM 2019-IEEE Conference on Computer Communications. IEEE, 2019, pp. 1459–1467

    2019

  21. [29]

    Service placement and request scheduling for data- intensive applications in edge clouds,

    V . Farhadi, F. Mehmeti, T. He, T. La Porta, H. Khamfroush, S. Wang, and K. S. Chan, “Service placement and request scheduling for data- intensive applications in edge clouds,” in IEEE INFOCOM 2019-IEEE Conference on Computer Communications . IEEE, 2019, pp. 1279– 1287

    2019

  22. [30]

    Adaptive user- managed service placement for mobile edge computing: An online learning approach,

    T. Ouyang, R. Li, X. Chen, Z. Zhou, and X. Tang, “Adaptive user- managed service placement for mobile edge computing: An online learning approach,” in IEEE INFOCOM 2019-IEEE Conference on Computer Communications. IEEE, 2019, pp. 1468–1476

    2019

  23. [31]

    Schrijver, Combinatorial optimization: polyhedra and efficiency

    A. Schrijver, Combinatorial optimization: polyhedra and efficiency . Springer Science & Business Media, 2003, vol. 24

    2003

  24. [32]

    The ellipsoid method and its consequences in combinatorial optimization,

    M. Grötschel, L. Lovász, and A. Schrijver, “The ellipsoid method and its consequences in combinatorial optimization,” Combinatorica, vol. 1, no. 2, pp. 169–197, 1981. 13

    1981

  25. [33]

    On submodular function minimization,

    W. H. Cunningham, “On submodular function minimization,” Combina- torica, vol. 5, no. 3, pp. 185–192, 1985

    1985

  26. [34]

    A combinatorial strongly polynomial algorithm for minimizing submodular functions,

    S. Iwata, L. Fleischer, and S. Fujishige, “A combinatorial strongly polynomial algorithm for minimizing submodular functions,” Journal of the ACM (JACM) , vol. 48, no. 4, pp. 761–777, 2001

    2001

  27. [35]

    Computers and intractability. a guide to the theory of np-completeness,

    H. R. Lewis, “Computers and intractability. a guide to the theory of np-completeness,” 1983

    1983

  28. [36]

    A tight linear time (1/2)-approximation for unconstrained submodular maximization,

    N. Buchbinder, M. Feldman, J. Seffi, and R. Schwartz, “A tight linear time (1/2)-approximation for unconstrained submodular maximization,” SIAM Journal on Computing , vol. 44, no. 5, pp. 1384–1402, 2015

    2015

  29. [37]

    Submodular approximation: Sampling- based algorithms and lower bounds,

    Z. Svitkina and L. Fleischer, “Submodular approximation: Sampling- based algorithms and lower bounds,” SIAM Journal on Computing , vol. 40, no. 6, pp. 1715–1737, 2011

    2011

  30. [38]

    A note on maximizing a submodular set function subject to a knapsack constraint,

    M. Sviridenko, “A note on maximizing a submodular set function subject to a knapsack constraint,” Operations Research Letters , vol. 32, no. 1, pp. 41–43, 2004

    2004

  31. [39]

    Some simplified np- complete problems,

    M. R. Garey, D. S. Johnson, and L. Stockmeyer, “Some simplified np- complete problems,” in Proceedings of the sixth annual ACM symposium on Theory of computing , 1974, pp. 47–63

    1974

  32. [40]

    The storage versus repair- bandwidth trade-off for clustered storage systems,

    N. Prakash, V . Abdrashitov, and M. Médard, “The storage versus repair- bandwidth trade-off for clustered storage systems,” IEEE Transactions on Information Theory , vol. 64, no. 8, pp. 5783–5805, 2018

    2018

  33. [41]

    Learning to discover social circles in ego networks,

    J. Leskovec and J. Mcauley, “Learning to discover social circles in ego networks,” Advances in neural information processing systems , vol. 25, 2012

    2012

  34. [42]

    Data analysis in public social networks,

    L. Takac and M. Zabovsky, “Data analysis in public social networks,” in International scientific conference and international workshop present day trends of innovations , vol. 1, no. 6, 2012

    2012

  35. [43]

    Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters,

    J. Leskovec, K. J. Lang, A. Dasgupta, and M. W. Mahoney, “Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters,” Internet Mathematics, vol. 6, no. 1, pp. 29–123, 2009

    2009

  36. [44]

    Sfo: A toolbox for submodular function optimization,

    A. Krause, “Sfo: A toolbox for submodular function optimization,” The Journal of Machine Learning Research , vol. 11, pp. 1141–1144, 2010

    2010

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.