Pith. sign in

REVIEW 1 major objections 4 minor 59 references

Parameterized Complexity of Caching in Networks

T0 review · 1 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash

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

Pith's one-line read The paper establishes the exact parameterized complexity of network caching when contents have binary, unary, or unit sizes, and shows that all open homogeneous parameterizations are equivalent to each other.

desk verdict Solid, systematic complexity map for network caching; main results hold up, but Theorem 12's W[1]-hardness claim is invalid as stated. read the letter →

arxiv 2412.16585 v1 pith:ZXQXL3IS submitted 2024-12-21 cs.NI cs.CC

Robert Ganian , Fionn Mc Inerney , Dimitra Tsigkari This is my paper · ORCID
classification cs.NIcs.CC
keywords networkcachingcachehitrateparameterizedcomplexityfixed-parametertractabilityNP-hardnessW[1]-hardnessbipartitegraphscontentdeliverynetworks
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 asks when an optimal allocation of contents to caches in a user–cache network can be computed exactly rather than approximated, and answers the question with a full parameterized-complexity map. The answer depends sharply on how content sizes are encoded and which network quantities are small: with binary sizes, the problem is fixed-parameter tractable only when the number of contents is combined with the number of caches or users, and NP-hard in every other natural parameterization, even for one cache and one user. With unary sizes, new tractable islands appear, such as bounded caches plus bounded capacities, alongside W[1]-hardness results that rule out fixed-parameter algorithms for combinations like caches plus users. In the homogeneous unit-size case, the problem is XP in the number of users, and the paper proves that all of its still-open parameterizations are interreducible, so one answer settles them all. This matters because it tells content-delivery and edge-inference engineers exactly which small network dimensions make exact optimization feasible.

What carries the argument

The load-bearing objects are three variants of NETWORK-CACHING defined by content-size encoding: HOMNC (all sizes 1), HETNC-U (unary sizes), and HETNC-B (binary sizes). The arguments are carried by two families of tools: exact algorithms—brute-force branching over all allocations, dynamic programming over arrays indexed by remaining cache capacities, and a type-compression that groups caches by their user neighborhoods—and parameterized reductions from UNARY BIN PACKING, 0-1 KNAPSACK, MONOTONE NAE-3-SAT-B3, PLANAR 3-SAT-E3, and MAXIMUM k-VERTEX COVER. A key structural observation is that under the set-based hit-rate objective, contents stored in several caches serving the same user yield no additional hit, which justifies merging or splitting caches by neighborhood and powers both the algorithms and the equivalence reductions.

What would settle it

Encode a small 0-1 knapsack instance—say items of weights 2, 3, 5 with values 3, 4, 6 in a knapsack of capacity 5—as the single-cache, single-user HETNC-B instance described in Theorem 10. If the maximum normalized hit rate exceeds the normalized target when the knapsack answer is no, or falls below it when the answer is yes, the claimed reduction does not preserve the yes/no answer and the central landscape would need revision.

Watch

Extended reading notes

Core claim

The central claim is that NETWORK-CACHING has a complete, exact complexity landscape determined by the encoding of content sizes and by which of six parameters—number of caches C, maximum capacity K, number of contents S, number of users U, maximum degree Δ, and maximum requests per user λ—are bounded. In the binary-size variant HETNC-B, the paper proves FPT for C+S and U+S and paraNP-hardness for every remaining parameterization, including C alone, U alone, and S alone. In the unary variant HETNC-U, FPT holds for C+S, U+S, and C+K, XP holds for C and for U+K, W[1]-hardness holds for C+U and C+λ, and everything else is paraNP-hard. In the homogeneous variant HOMNC, XP holds already for U alone, and six parameterizations—C, U, U+K, C+U, C+λ, and the vertex cover number—are shown interreducible, leaving one open complexity question for all of them. The paper also shows that standard structural restrictions (treewidth, treedepth, feedback edge number, planarity) do not restore tractability except for the vertex-cover-number parameterization, which is absorbed into the equivalent open class.

Load-bearing premise

The results rely on the cache hit rate being the sum, over users, of the weights of contents stored somewhere in that user's adjacent caches; a requested content is either hit or not for each user, regardless of how many distinct caches hold it. If a deployment's actual objective counted hits per cache or per edge, the merging and type-splitting steps that make many of the algorithms and reductions work would no longer be valid.

Editorial extensions

If this is right

  • Exact optimal caching is feasible in practice exactly when content count plus cache count or content count plus user count stays small; outside those regimes, exact allocation is intractable.
  • For heterogeneous unary sizes, bounding cache capacity together with cache count or user count gives fixed-parameter algorithms, so capacity-aware CDN configurations are promising targets.
  • The homogeneous problem cannot be solved in polynomial time even with only two contents, two requests per user, unit capacities, and maximum degree 3, unless P=NP.
  • All open homogeneous parameterizations stand or fall together: proving W[1]-hardness for any one settles all five plus the vertex-cover-number case.
  • Structural graph restrictions such as planarity, treewidth, or treedepth do not make the problem tractable for the heterogeneous variants.

Reading between the lines

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

  • Editorial inference: the equivalence of the open HOMNC parameterizations suggests the missing W[1]-hardness proofs are likely to be found by strengthening the MAXIMUM k-VERTEX COVER or PLANAR 3-SAT-E3 gadgets rather than by discovering a new FPT algorithm.
  • Editorial inference: if real deployments count cache hits per cache or per edge rather than per user-content pair, the merging reductions in Corollary 2, Observation 5, and Theorem 14 could fail; a per-edge objective should be re-analyzed.
  • Editorial inference: the XP algorithms suggest practical exact solvers for instances with small numbers of caches or users, and can be adapted to any objective computable in FPT time, including quality-of-service or energy metrics.
  • Editorial inference: because the reductions from bin packing and knapsack are so tight, the results likely transfer directly to caching for edge-AI inference delivery, where content sizes are model artifacts and request catalogs are small.
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

1 major / 4 minor

Summary. The paper gives a parameterized complexity analysis of the proactive network-caching problem in the bipartite users/caches model. Three variants are studied: homogeneous contents (HOMNC), heterogeneous contents with unary-encoded sizes (HETNC-U), and heterogeneous contents with binary-encoded sizes (HETNC-B). The parameters considered are the number of caches C, maximum cache capacity K, number of contents S, number of users U, maximum degree Δ, and maximum number of contents requested per user λ. The main results are: FPT algorithms for HETNC-B under C+S and U+S; FPT/XP results for HETNC-U under C+K, C, and U+K; XP for HOMNC parameterized by U; paraNP-hardness results for all remaining single-parameter cases (with Theorem 7 showing NP-hardness even when S=λ=2, K=1, Δ=3); W[1]-hardness for HETNC-U parameterized by C; and a theorem (Theorem 14) showing that six open parameterizations of HOMNC are interreducible. The paper also studies structural parameters such as treewidth, treedepth, vertex cover number, and planarity.

Significance. If the main results stand, the paper provides a nearly complete parameterized complexity map for a practically motivated caching problem and correctly identifies the few remaining open frontier cases. The upper-bound algorithms are explicit, deterministic, and accompanied by detailed correctness proofs; the hardness proofs use standard, well-established source problems (Monotone NAE-3-SAT, Unary Bin Packing, 0-1 Knapsack, Planar 3-SAT). The interreducibility result in Theorem 14 is a useful and nontrivial contribution, since it reduces the open cases to a single conjecture. The paper is also careful to state which parameterizations remain open. However, one claimed lower bound, the W[1]-hardness assertion in Theorem 12, is not valid as written, and this must be corrected before the paper can be accepted.

major comments (1)
  1. [Section 5, Theorem 12] The claim 'Moreover, in this case it is also W[1]-hard parameterized by K' is not established by the given proof. The reduction is from MAXIMUM k-VERTEX COVER parameterized by k, but that problem is FPT (it is the standard Partial Vertex Cover problem, which admits FPT algorithms and kernelization for parameter k). A parameterized reduction from an FPT problem cannot prove W[1]-hardness unless FPT = W[1]. Hence the W[1]-hardness statement in Theorem 12 should be removed, or the proof should be replaced with a reduction from a known W[1]-hard problem such as Multicolored Clique. The NP-hardness part of Theorem 12 and its consequences for treewidth, treedepth, feedback edge number, and planarity remain valid, since the NP-hardness proof is independent of the W[1]-hardness claim.
minor comments (4)
  1. [Section 6, Theorem 14, Case 5] The bound on the number of caches and users after the reduction appears undercounted: distinct neighborhoods for caches in I and for users in I are each bounded by 2^{|X|}, so the total should be at most 2^{|X|}+2^{|X|}+2|X| rather than 2^{|X|}+|X|. This does not affect the conclusion, since both bounds are functions of vc(G), but the displayed inequality should be corrected.
  2. [Introduction and Section 6] The text says 'all 5 open parameterizations for HOMNC', but the list that follows contains six items: C, U, U+K, C+U, C+λ, and the vertex cover number. The count should be adjusted for consistency.
  3. [Corollary 2] The runtime expression in Corollary 2 is unwieldy and the exponents are easy to misread; a cleaner statement such as O(C log C U + f(U,S)) with f(U,S)=2^{O(S^2 2^U)} would improve readability.
  4. [Figure 1] The figure legend for the bottom landscape should clarify which 'XP' regions are open for W[1]-hardness and which 'XP & W[1]-hard' regions are already resolved, since this distinction is central to the paper's claims.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the complexity boundaries are derived from independent source problems and self-contained algorithms.

full rationale

The paper's derivation chain is anchored externally at every load-bearing step. Upper bounds are proved by explicit brute-force enumeration (Theorem 1), dynamic programming over capacity arrays (Theorems 3 and 4), or cache-reduction arguments (Corollary 2, Observation 5, Corollary 6); none of these assume the tractability they establish. Lower bounds reduce from independent NP-hard or W[1]-hard problems: MONOTONE NAE-3-SAT-B3 (Theorem 7), UNARY BIN PACKING (Theorem 8, Corollary 9), 0-1 KNAPSACK (Theorem 10, Corollary 11), MAXIMUM k-VERTEX COVER (Theorem 12), and PLANAR 3-SAT-E3 (Theorem 13). None of these source problems is defined in terms of the caching variants, and the reductions construct caching instances explicitly. The interreducibility theorem (Theorem 14) is a formal equivalence between open parameterizations, proved by explicit polynomial-time transformations; it does not presuppose the conjectured W[1]-hardness, so it is not circular either. Citations of the authors' own prior work appear only as related-work context or as background for structural parameters (e.g., feedback edge number, Bayesian network learning), and they are not used to justify the paper's central claims. One correctness concern is worth recording but it is not a circularity: the W[1]-hardness component of Theorem 12 reduces from MAXIMUM k-VERTEX COVER, which is FPT parameterized by k, so that proof cannot establish W[1]-hardness as written. This is an unsound-reduction error, not a self-referential or fitted-input step, and the main complexity landscape does not rely on it because HOMNC is already paraNP-hard when K=1 by Theorem 7. Overall, no equation is defined in terms of its own target result, no fitted parameter is renamed as a prediction, and no load-bearing argument reduces to a self-citation chain.

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

The central claims rest on standard NP-hardness and W[1]-hardness results imported from the literature, plus the domain assumption that the cache hit rate is the additive, set-based objective defined in Section 2. No free parameters are fitted. No new entities are introduced.

assumptions (6)
  • standard math MONOTONE NAE-3-SAT-B3 is NP-hard (Kratochvíl and Tuza, 2002)
    Used in Theorem 7 to prove NP-hardness of HOMNC with S=lambda=2, K=1, Delta=3.
  • standard math UNARY BIN PACKING is NP-hard and W[1]-hard parameterized by the number of bins (Jansen et al., 2013)
    Used in Theorem 8 and Corollary 9 to prove W[1]-hardness of HETNC-U parameterized by C.
  • standard math 0-1 KNAPSACK is NP-hard (Garey and Johnson, 1979)
    Used in Theorem 10 and Corollary 11 to prove paraNP-hardness of HETNC-B.
  • standard math PLANAR 3-SAT-E3 is NP-hard (Middendorf and Pfeiffer, 1993)
    Used in Theorem 13 to prove NP-hardness of HOMNC on planar bounded-degree networks.
  • standard math MAXIMUM k-VERTEX COVER is NP-hard and, per the paper, W[1]-hard parameterized by k
    Used in Theorem 12. The NP-hardness is standard, but the W[1]-hardness claim is not referenced and appears to be false, making this axiom load-bearing only for the flawed part.
  • domain assumption Cache hit rate is additive and set-based: a user's hit is counted once per content stored in at least one adjacent cache
    Section 2 defines CH(Z) with H(u) as a set; all algorithms and reductions rely on this semantics.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Parameterized Complexity of Caching in Networks." pith.science (2026). https://pith.science/paper/ZXQXL3IS

@misc{pith2026241216585,
  author       = {Pith},
  title        = {Pith review of: Parameterized Complexity of Caching in Networks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZXQXL3IS}},
  note         = {Machine review of arXiv:2412.16585}
}
read the original abstract

The fundamental caching problem in networks asks to find an allocation of contents to a network of caches with the aim of maximizing the cache hit rate. Despite the problem's importance to a variety of research areas -- including not only content delivery, but also edge intelligence and inference -- and the extensive body of work on empirical aspects of caching, very little is known about the exact boundaries of tractability for the problem beyond its general NP-hardness. We close this gap by performing a comprehensive complexity-theoretic analysis of the problem through the lens of the parameterized complexity paradigm, which is designed to provide more precise statements regarding algorithmic tractability than classical complexity. Our results include algorithmic lower and upper bounds which together establish the conditions under which the caching problem becomes tractable.

Figures

Figures reproduced from arXiv: 2412.16585 by the authors.

Figure 1
Figure 1. Complexity landscapes of HETNC-B (top), HETNC-U (middle), and HOMNC (bottom). We (mostly) omit parameterizations including C + ∆, U + ∆, U + λ, or S + λ, as the first two, the third, and the last are complexity￾theoretically equivalent to C+U, U +S, and S, respectively. Indeed, for any pair of combined parameters claimed to be equivalent, each of them can be bounded by a computable function of the other. To prove th… view at source ↗
Figure 2
Figure 2. Illustration of a bipartite graph between users and [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 1
Figure 1. 2 Setup and Problem Definitions We use standard graph-theoretic terminology (Diestel, 2012). For any positive integer n, let [n] = {1, . . . , n}. We consider a set C of C := |C| caches and a set U of U := |U| users, each of which has access to a subset of caches (which could be determined by, e.g., routing or other network poli￾cies). This naturally defines a bipartite graph G = (C, U, E), where E are the edges bet… view at source ↗
Figures from the paper (2 more)
Figure 3
Figure 3. Figure 3: Illustration of the subdivided star G′ constructed in the proof of Theorem 12, where ab, aq, and xy are edges in the graph G from the instance of MAXIMUM k-VERTEX COVER. (of weight 1) in G′ that only requests (with non-zero prob￾ability) the contents x and y with equal…
Figure 4
Figure 4. Figure 4: Illustration of the planar graph G constructed from an instance ϕ of PLANAR 3-SAT-E3 in the proof of Theo￾rem 13. Here, ϕ contains the clause C1 containing the vari￾ables x1, x2, and a third arbitrary one (denoted by a line pro￾truding from the vertex uC1 ), the clause…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

59 extracted references · 59 canonical work pages

  1. [1]

    a ckstr \

    B \"a ckstr \"o m, C., Chen, Y., Jonsson, P., Ordyniak, S., and Szeider, S. (2012). The complexity of planning revisited—a parameterized analysis. In Proc. of AAAI 2012 , volume 26, pages 1735--1741

    work page 2012

  2. [2]

    Bastug, E., Bennis, M., and Debbah, M. (2014). Living on the edge: The role of proactive caching in 5G wireless networks. IEEE Communications Magazine , 52(8):82--89

    work page 2014

  3. [3]

    Bhattacharjee, R., Banerjee, S., and Sinha, A. (2020). Fundamental limits on the regret of online network-caching. Proc. of the ACM on Measurement and Analysis of Computing Systems , 4(2):1--31

    work page 2020

  4. [4]

    and Giovanidis, A

    Blaszczyszyn, B. and Giovanidis, A. (2015). Optimal geographic caching in cellular networks. In Proc. of IEEE ICC 2015 , pages 3358--3363

    work page 2015

  5. [5]

    Bliem, B., Bredereck, R., and Niedermeier, R. (2016). Complexity of efficient and envy-free resource allocation: few agents, resources, or utility levels. In Proc. of IJCAI 2016 , pages 102--108

    work page 2016

  6. [6]

    L., Groenland, C., and Pilipczuk, M

    Bodlaender, H. L., Groenland, C., and Pilipczuk, M. (2023). Parameterized complexity of binary CSP: vertex cover, treedepth, and related parameters. In Proc. of ICALP 2023 , volume 261 of LIPIcs , pages 27:1--27:20. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik

    work page 2023

  7. [7]

    Bredereck, R., Heeger, K., Knop, D., and Niedermeier, R. (2022). Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters. Inf. Comput. , 289:104943

    work page 2022

  8. [8]

    Chalopin, J., Chepoi, V., Mc Inerney , F., and Ratel, S. (2024). Non-clashing teaching maps for balls in graphs. In Proc. of COLT 2024 , volume 247 of PMLR , pages 840--875

    work page 2024

Show all 59 references
  1. [9]

    V., Kowalik, ., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, S

    Cygan, M., Fomin, F. V., Kowalik, ., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, S. (2015). Parameterized Algorithms . Springer

    2015

  2. [10]

    Dehghan, M., Jiang, B., Seetharam, A., He, T., Salonidis, T., Kurose, J., Towsley, D., and Sitaraman, R. (2016). On the complexity of optimal request routing and content caching in heterogeneous cache networks. IEEE/ACM Trans. on Networking , 25(3):1635--1648

    2016

  3. [11]

    Deligkas, A., Eiben, E., Ganian, R., Hamm, T., and Ordyniak, S. (2021). The parameterized complexity of connected fair division. In Proc. of IJCAI 2021 , pages 139--145

    2021

  4. [12]

    Diestel, R. (2012). Graph Theory, 4th Edition , volume 173 of Graduate texts in mathematics . Springer

    2012

  5. [13]

    Disney+ pricing

    D isney+ (2023). Disney+ pricing. https://help.disneyplus.com/article/disneyplus-price

    2023

  6. [14]

    Downey, R. G. and Fellows, M. R. (2013). Fundamentals of Parameterized Complexity . Texts in Computer Science. Springer

    2013

  7. [15]

    Eiben, E., Ganian, R., Hamm, T., and Ordyniak, S. (2023). Parameterized complexity of envy-free resource allocation in social networks. Artificial Intelligence , 315:103826

    2023

  8. [16]

    Eiben, E., Ganian, R., Kanj, I., Ordyniak, S., and Szeider, S. (2021). The parameterized complexity of clustering incomplete data. In Proc. of AAAI 2021 , volume 35, pages 7296--7304

    2021

  9. [17]

    Ganian, R., Kanj, I., Ordyniak, S., and Szeider, S. (2020). On the parameterized complexity of clustering incomplete data into subspaces of small rank. In Proc. of AAAI 2020 , volume 34, pages 3906--3913

    2020

  10. [18]

    A., Ordyniak, S., and Szeider, S

    Ganian, R., Kanj, I. A., Ordyniak, S., and Szeider, S. (2018). Parameterized algorithms for the matrix completion problem. In Proc. of ICML 2018 , volume 80 of PMLR , pages 1642--1651

    2018

  11. [19]

    and Korchemna, V

    Ganian, R. and Korchemna, V. (2021). The complexity of B ayesian network learning: Revisiting the superstructure. In Proc. of NeurIPS 2021 , volume 34, pages 430--442

    2021

  12. [20]

    Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman

    1979

  13. [21]

    and Komusiewicz, C

    Gr \"u ttemeier, N. and Komusiewicz, C. (2022). Learning B ayesian networks under sparsity constraints: A parameterized complexity analysis. Journal of Artificial Intelligence Research , 74:1225--1267

    2022

  14. [22]

    and Yeh, E

    Ioannidis, S. and Yeh, E. (2016). Adaptive caching networks with optimality guarantees. ACM SIGMETRICS Performance Evaluation Review , 44(1):113--124

    2016

  15. [23]

    Jansen, K., Kratsch, S., Marx, D., and Schlotter, I. (2013). Bin packing with fixed number of bins revisited. Journal of Computer and System Sciences , 79(1):39--49

    2013

  16. [24]

    Komusiewicz, C., Schramek, J., and Sommer, F. (2023). On the group coverage centrality problem: Parameterized complexity and heuristics. In Proc. of ACDA 2023 , pages 13--24

    2023

  17. [25]

    and Tuza, Z

    Kratochv\' i l, J. and Tuza, Z. (2002). On the complexity of bicoloring clique hypergraphs of graphs. J. Algorithms , 45:40--54

    2002

  18. [26]

    Krolikowski, J., Giovanidis, A., and Di Renzo, M. (2018). A decomposition framework for optimal edge-cache leasing. IEEE Journal on Selected Areas in Communications , 36(6):1345--1359

    2018

  19. [27]

    Lindgren, E., Reddi, S., Guo, R., and Kumar, S. (2021). Efficient training of retrieval models using negative cache. In Proc. of NeurIPS 2021 , volume 34, pages 4134--4146

    2021

  20. [28]

    Liu, D., Chen, B., Yang, C., and Molisch, A. F. (2016). Caching at the wireless edge: design aspects, challenges, and future directions. IEEE Communications Magazine , 54(9):22--28

    2016

  21. [29]

    Maggi, L., Gkatzikis, L., Paschos, G., and Leguay, J. (2018). Adapting caching to audience retention rate. Computer Communications , 116:159--171

    2018

  22. [30]

    Mhaisen, N., Sinha, A., Paschos, G., and Iosifidis, G. (2022). Optimistic no-regret algorithms for discrete caching. Proc. of the ACM on Measurement and Analysis of Computing Systems , 6(3):1--28

    2022

  23. [31]

    and Pfeiffer, F

    Middendorf, M. and Pfeiffer, F. (1993). On the complexity of the disjoint paths problem. Combinatorica , 13(1):97--107

    1993

  24. [32]

    and de Mendez, P

    Nesetril, J. and de Mendez, P. O. (2012). Sparsity - Graphs, Structures, and Algorithms , volume 28 of Algorithms and combinatorics . Springer

    2012

  25. [33]

    Plans and pricing

    N etflix (2023). Plans and pricing. https://help.netflix.com/en/node/24926

    2023

  26. [34]

    O pen C onnect appliances

    N etflix (2024a). O pen C onnect appliances. https://openconnect.netflix.com/en/appliances/

    2024

  27. [35]

    O pen C onnect fill patterns

    N etflix (2024b). O pen C onnect fill patterns. https://openconnect.zendesk.com/hc/en-us/articles/360035618071-Fill-patterns

    2024

  28. [36]

    N etflix and F ill

    N etflix T ech B log (2016). N etflix and F ill. https://netflixtechblog.com/netflix-and-fill-c43a32b490c0

    2016

  29. [37]

    and Szeider, S

    Ordyniak, S. and Szeider, S. (2013). Parameterized complexity results for exact B ayesian network structure learning. Journal of Artificial Intelligence Research , 46:263--302

    2013

  30. [38]

    and Sinha, A

    Paria, D. and Sinha, A. (2021). L ead C ache: Regret-optimal caching in networks. In Proc. of NeurIPS 2021 , volume 34, pages 4435--4447

    2021

  31. [39]

    Paschos, G., Iosifidis, G., and Caire, G. (2020). Cache optimization models and algorithms. Foundations and Trends in Communications and Information Theory , 16(3--4):156--345

    2020

  32. [40]

    S., Bastug, E., Land, I., Caire, G., and Debbah, M

    Paschos, G. S., Bastug, E., Land, I., Caire, G., and Debbah, M. (2016). Wireless caching: Technical misconceptions and business barriers. IEEE Communications Magazine , 54(8):16--22

    2016

  33. [41]

    S., Destounis, A., Vigneri, L., and Iosifidis, G

    Paschos, G. S., Destounis, A., Vigneri, L., and Iosifidis, G. (2019). Learning to cache with no regrets. In Proc. of IEEE INFOCOM 2019 , pages 235--243

    2019

  34. [42]

    S., Iosifidis, G., Tao, M., Towsley, D., and Caire, G

    Paschos, G. S., Iosifidis, G., Tao, M., Towsley, D., and Caire, G. (2018). The role of caching in future communication systems and networks. IEEE Journal on Selected Areas in Communications , 36(6):1111--1125

    2018

  35. [43]

    Poularakis, K., Iosifidis, G., Argyriou, A., Koutsopoulos, I., and Tassiulas, L. (2019). Distributed caching algorithms in the realm of layered video streaming. IEEE Trans. on Mobile Computing , 18(4):757--770

    2019

  36. [44]

    Poularakis, K., Iosifidis, G., Argyriou, A., and Tassiulas, L. (2014a). Video delivery over heterogeneous cellular networks: Optimizing cost and performance. In Proc. of IEEE INFOCOM 2014 , pages 1078--1086

    2014

  37. [45]

    Poularakis, K., Iosifidis, G., and Tassiulas, L. (2014b). Approximation algorithms for mobile data caching in small cell networks. IEEE Trans. on Communications , 62(10):3665--3677

    2014

  38. [46]

    I., Tuholukova, A., Neglia, G., and Spyropoulos, T

    Ricardo, G. I., Tuholukova, A., Neglia, G., and Spyropoulos, T. (2021). Caching policies for delay minimization in small cell networks with coordinated multi-point joint transmissions. IEEE/ACM Trans. on Networking , 29(3):1105--1115

    2021

  39. [47]

    and Seymour, P

    Robertson, N. and Seymour, P. D. (1986). Graph minors. II. A lgorithmic aspects of tree-width. J. Algorithms , 7(3):309--322

    1986

  40. [48]

    Rohatgi, D. (2020). Near-optimal bounds for online caching with machine learned advice. In Proc. of SODA 2020 , pages 1834--1845

    2020

  41. [49]

    Rost, M., D \"o hne, E., and Schmid, S. (2019). Parametrized complexity of virtual network embeddings: Dynamic & linear programming approximations. ACM SIGCOMM Computer Communication Review , 49(1):3--10

    2019

  42. [50]

    S., Castellano, G., Neglia, G., Pianese, F., and Araldo, A

    Salem, T. S., Castellano, G., Neglia, G., Pianese, F., and Araldo, A. (2023). Toward inference delivery networks: Distributing machine learning with optimality guarantees. IEEE/ACM Trans. on Networking

    2023

  43. [51]

    G., Molisch, A

    Shanmugam, K., Golrezaei, N., Dimakis, A. G., Molisch, A. F., and Caire, G. (2013). Femtocaching: Wireless content delivery through distributed caching helpers. IEEE Trans. on Information Theory , 59(12):8402--8413

    2013

  44. [52]

    and Eryilmaz, A

    Tadrous, J. and Eryilmaz, A. (2015). On optimal proactive caching for mobile networks with demand uncertainties. IEEE/ACM Trans. on Networking , 24(5):2715--2727

    2015

  45. [53]

    Thapa, C., Arachchige, P. C. M., Camtepe, S., and Sun, L. (2022). Splitfed: When federated learning meets split learning. In Proc. of AAAI 2022 , volume 36, pages 8485--8493

    2022

  46. [54]

    Tirana, J., Tsigkari, D., Iosifidis, G., and Chatzopoulos, D. (2024). Workflow optimization for parallel split learning. In Proc. of IEEE INFOCOM 2024

    2024

  47. [55]

    and Spyropoulos, T

    Tsigkari, D. and Spyropoulos, T. (2022). An approximation algorithm for joint caching and recommendations in cache networks. IEEE Trans. on Network and Service Management , 19(2):1826--1841

    2022

  48. [56]

    Yu, Z., Li, H., Fu, F., Miao, X., and Cui, B. (2024). Accelerating text-to-image editing via cache-enabled sparse diffusion inference. In Proc. of AAAI 2024 , volume 38, pages 16605--16613

    2024

  49. [57]

    Zhang, Z., Shao, W., Ge, Y., Wang, X., Gu, J., and Luo, P. (2024). Cached transformers: Improving transformers with differentiable memory cachde. In Proc. of AAAI 2024 , volume 38, pages 16935--16943

    2024

  50. [58]

    Zhou, R., Khemmarat, S., and Gao, L. (2010). The impact of Y ou T ube recommendation system on video views. In Proc. of IMC 2010 , pages 404--410

    2010

  51. [59]

    Zhu, B., Sheng, Y., Zheng, L., Barrett, C., Jordan, M., and Jiao, J. (2023). Towards optimal caching and model selection for large model inference. In Proc. of NeurIPS 2023 , volume 36, pages 59062--59094

    2023

Pith tools

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