Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2412.16585 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929644186370048 |
|---|---|
| author | Ganian, Robert Inerney, Fionn Mc Tsigkari, Dimitra |
| author_facet | Ganian, Robert Inerney, Fionn Mc Tsigkari, Dimitra |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_16585 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Parameterized Complexity of Caching in Networks Ganian, Robert Inerney, Fionn Mc Tsigkari, Dimitra Networking and Internet Architecture Computational Complexity 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. |
| title | Parameterized Complexity of Caching in Networks |
| topic | Networking and Internet Architecture Computational Complexity |
| url | https://arxiv.org/abs/2412.16585 |