{"authors":[{"id":null,"fullName":"Robert Ganian","name":null,"surname":null,"rank":1,"pid":null},{"id":null,"fullName":"Fionn Mc Inerney","name":null,"surname":null,"rank":2,"pid":null},{"id":null,"fullName":"Dimitra Tsigkari","name":null,"surname":null,"rank":3,"pid":null}],"openAccessColor":null,"publiclyFunded":false,"eoscIfGuidelines":null,"type":"publication","language":{"code":"und","label":"Undetermined"},"countries":null,"subjects":[{"subject":{"scheme":"keyword","value":"Computer Science - Networking and Internet Architecture"},"provenance":null},{"subject":{"scheme":"keyword","value":"Networking and Internet Architecture (cs.NI)"},"provenance":null},{"subject":{"scheme":"keyword","value":"FOS: Computer and information sciences"},"provenance":null},{"subject":{"scheme":"keyword","value":"Computer Science - Computational Complexity"},"provenance":null},{"subject":{"scheme":"keyword","value":"Network of Caches"},"provenance":null},{"subject":{"scheme":"FOS","value":"0102 computer and information sciences"},"provenance":null},{"subject":{"scheme":"keyword","value":"Fixed-parameter Tractability"},"provenance":null},{"subject":{"scheme":"keyword","value":"Caching"},"provenance":null},{"subject":{"scheme":"keyword","value":"Computational Complexity (cs.CC)"},"provenance":null},{"subject":{"scheme":"FOS","value":"01 natural sciences"},"provenance":null},{"subject":{"scheme":"keyword","value":"Parameterized Complexity"},"provenance":null}],"mainTitle":"Parameterized Complexity of Caching in Networks","subTitle":null,"descriptions":["<jats:p>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.</jats:p>"],"publicationDate":"2025-04-11","publisher":"Association for the Advancement of Artificial Intelligence (AAAI)","embargoEndDate":"2024-12-01","sources":["Crossref"],"formats":null,"contributors":null,"coverages":null,"bestAccessRight":{"code":"c_abf2","label":"OPEN","scheme":"http://vocabularies.coar-repositories.org/documentation/access_rights/"},"container":{"name":"Proceedings of the AAAI Conference on Artificial Intelligence","issnPrinted":"2159-5399","issnOnline":"2374-3468","issnLinking":null,"ep":"11237","iss":null,"sp":"11229","vol":"39","edition":null,"conferencePlace":null,"conferenceDate":null},"documentationUrls":null,"codeRepositoryUrl":null,"programmingLanguage":null,"contactPeople":null,"contactGroups":null,"tools":null,"size":null,"version":null,"geoLocations":null,"id":"doi_dedup___::73deda5619ce14dfe2a1318d6abfe259","originalIds":["10.1609/aaai.v39i11.33221","50|doiboost____|b40b36032e8d342e661fb987ac376262","50|datacite____::73deda5619ce14dfe2a1318d6abfe259","10.48550/arxiv.2412.16585","50|datacite____::b5e71265b5009651bd9c271640ddccd4","10.5281/zenodo.14748609","50|od______2659::b5e71265b5009651bd9c271640ddccd4","oai:zenodo.org:14748609","50|datacite____::fe1ca89ce14ab162a35a841b542352e1","10.5281/zenodo.14748608","50|od________18::27850193cae25252d80c54aa72870913","oai:arXiv.org:2412.16585","50|dblp________::aca16b8c57a4a047b373015668e33776","50|dblp________::bad8a9d7e26a5213f36e24131539006e"],"pids":[{"scheme":"doi","value":"10.1609/aaai.v39i11.33221"},{"scheme":"doi","value":"10.48550/arxiv.2412.16585"},{"scheme":"doi","value":"10.5281/zenodo.14748609"},{"scheme":"doi","value":"10.5281/zenodo.14748608"},{"scheme":"arXiv","value":"2412.16585"}],"dateOfCollection":null,"lastUpdateTimeStamp":null,"indicators":{"citationImpact":{"citationCount":0.0,"influence":2.1746283E-9,"popularity":2.2497804E-9,"impulse":0.0,"citationClass":"C5","influenceClass":"C5","impulseClass":"C5","popularityClass":"C5"}},"projects":[{"id":"corda_____he::352a84fb7feeb560b967c83edda2bac5","code":"101139067","acronym":"ELASTIC","title":"Efficient, portabLe And Secure orchesTration for reliable servICes","funder":"European Commission","pids":[{"scheme":"doi","value":"10.3030/101139067"}]},{"id":"corda_____he::ca9d0ce42b3cb57bb6c93e1398f53ded","code":"101093006","acronym":"TaRDIS","title":"Trustworthy and Resilient Decentralised Intelligence for Edge Systems","funder":"European Commission","pids":[{"scheme":"doi","value":"10.3030/101093006"}]}],"organizations":[{"legalName":"TU Wien","acronym":"TU Wien","id":"pending_org_::f0c45462052d6218c9b5e1dc3c6d1c2e","pids":null,"countries":[{"code":"AT","label":"Austria"}],"websiteurl":null},{"legalName":"TU Wien","acronym":"TISS","id":"pending_org_::32336c3c5a451fa2eb9bf983726dd318","pids":null,"countries":[{"code":"AT","label":"Austria"}],"websiteurl":"https://api.eurocris.org/dris/orgunits/ou01374"},{"legalName":"TU/WIEN","acronym":"TU/WIEN","id":"pending_org_::14ad8517ab8bf7658bf71ddfcc2a923a","pids":null,"countries":[{"code":"AT","label":"Austria"}],"websiteurl":null},{"legalName":"TU Wien","acronym":"TU Wien","id":"pending_org_::919707e27900949c39a317285097a6b0","pids":null,"countries":[{"code":"AT","label":"Austria"}],"websiteurl":null},{"legalName":"TU Wien","acronym":"TUW","id":"openorgs____::9d089cd60852c6e601104f886a677f28","pids":[{"scheme":"wikidata","value":"Q689400"},{"scheme":"OrgRef","value":"1267354"},{"scheme":"fundref","value":"100007223"},{"scheme":"FundRef","value":"501100012650"},{"scheme":"FundRef","value":"501100004729"},{"scheme":"FundRef","value":"100007223"},{"scheme":"GRID","value":"grid.5329.d"},{"scheme":"wikidata","value":"Q757615"},{"scheme":"ROR","value":"https://ror.org/04d836q62"},{"scheme":"ISNI","value":"0000000123484034"},{"scheme":"fundref","value":"501100012650"},{"scheme":"RRID","value":"RRID:SCR_011762"},{"scheme":"Wikidata","value":"Q757615"},{"scheme":"ISNI","value":"0000000419370669"},{"scheme":"fundref","value":"501100004729"},{"scheme":"PIC","value":"999979888"},{"scheme":"OrgReg","value":"AT0005"},{"scheme":"mag_id","value":"145847075"},{"scheme":"Wikidata","value":"Q689400"}],"countries":[{"code":"AT","label":"Austria"}],"websiteurl":"https://www.tuwien.at/"},{"legalName":"TU Wien","acronym":"TU Wien","id":"pending_org_::2e21494119d1e178e92e565209219c9e","pids":null,"countries":[{"code":"AT","label":"Austria"}],"websiteurl":null}],"communities":[{"code":"eosc","label":"EOSC","provenance":null}],"collectedFrom":[{"key":"openaire____::9e3be59865b2c1c335d32dae2fe7b254","value":"Datacite"},{"key":"opendoar____::358aee4cc897452c00244351e4d91f69","value":"ZENODO"},{"key":"openaire____::081b82f96300b6a6e3d282bad31cb6e2","value":"Crossref"},{"key":"openaire____::d8b68cc0a53121f6f896883a7d60c1db","value":"DBLP"},{"key":"opendoar____::6f4922f45568161a8cdf4ad2299f6d23","value":"arXiv.org e-Print Archive"}],"instances":[{"pids":[{"scheme":"doi","value":"10.1609/aaai.v39i11.33221"}],"type":"Article","urls":["https://doi.org/10.1609/aaai.v39i11.33221"],"publicationDate":"2025-04-11","refereed":"peerReviewed","hostedBy":{"key":"issn___print::c3eeaf213793b1a8aa96af199fd54aa4","value":"Proceedings of the AAAI Conference on Artificial Intelligence"},"collectedFrom":{"key":"openaire____::081b82f96300b6a6e3d282bad31cb6e2","value":"Crossref"}},{"pids":[{"scheme":"doi","value":"10.48550/arxiv.2412.16585"}],"license":"arXiv Non-Exclusive Distribution","type":"Article","urls":["https://dx.doi.org/10.48550/arxiv.2412.16585"],"publicationDate":"2024-01-01","refereed":"nonPeerReviewed","hostedBy":{"key":"openaire____::55045bd2a65019fd8e6741a755395c8c","value":"Unknown Repository"},"collectedFrom":{"key":"openaire____::9e3be59865b2c1c335d32dae2fe7b254","value":"Datacite"}},{"pids":[{"scheme":"doi","value":"10.5281/zenodo.14748609"}],"license":"CC BY","type":"Article","urls":["https://dx.doi.org/10.5281/zenodo.14748609"],"publicationDate":"2025-01-27","refereed":"nonPeerReviewed","hostedBy":{"key":"opendoar____::358aee4cc897452c00244351e4d91f69","value":"ZENODO"},"collectedFrom":{"key":"openaire____::9e3be59865b2c1c335d32dae2fe7b254","value":"Datacite"}},{"pids":[{"scheme":"doi","value":"10.5281/zenodo.14748609"}],"alternateIdentifiers":[{"scheme":"oai","value":"oai:zenodo.org:14748609"},{"scheme":"doi","value":"10.1609/aaai.v39i11.33221"}],"license":"CC BY","accessRight":{"code":"c_abf2","label":"OPEN","scheme":"http://vocabularies.coar-repositories.org/documentation/access_rights/","openAccessRoute":null},"type":"Conference object","urls":["http://dx.doi.org/10.5281/zenodo.14748609","https://zenodo.org/records/14748609"],"publicationDate":"2025-01-27","refereed":"nonPeerReviewed","hostedBy":{"key":"opendoar____::358aee4cc897452c00244351e4d91f69","value":"ZENODO"},"collectedFrom":{"key":"opendoar____::358aee4cc897452c00244351e4d91f69","value":"ZENODO"}},{"pids":[{"scheme":"doi","value":"10.5281/zenodo.14748608"}],"license":"CC BY","type":"Article","urls":["https://dx.doi.org/10.5281/zenodo.14748608"],"publicationDate":"2025-01-27","refereed":"nonPeerReviewed","hostedBy":{"key":"opendoar____::358aee4cc897452c00244351e4d91f69","value":"ZENODO"},"collectedFrom":{"key":"openaire____::9e3be59865b2c1c335d32dae2fe7b254","value":"Datacite"}},{"pids":[{"scheme":"arXiv","value":"2412.16585"}],"accessRight":{"code":"c_abf2","label":"OPEN","scheme":"http://vocabularies.coar-repositories.org/documentation/access_rights/","openAccessRoute":null},"type":"Preprint","urls":["http://arxiv.org/abs/2412.16585"],"publicationDate":"2024-12-21","refereed":"nonPeerReviewed","hostedBy":{"key":"opendoar____::6f4922f45568161a8cdf4ad2299f6d23","value":"arXiv.org e-Print Archive"},"collectedFrom":{"key":"opendoar____::6f4922f45568161a8cdf4ad2299f6d23","value":"arXiv.org e-Print Archive"}},{"alternateIdentifiers":[{"scheme":"doi","value":"10.48550/arxiv.2412.16585"}],"type":"Preprint","urls":["https://doi.org/10.48550/arXiv.2412.16585","https://dblp.org/rec/journals/corr/abs-2412-16585.html"],"publicationDate":"2024-01-01","refereed":"nonPeerReviewed","hostedBy":{"key":"openaire____::d8b68cc0a53121f6f896883a7d60c1db","value":"DBLP"},"collectedFrom":{"key":"openaire____::d8b68cc0a53121f6f896883a7d60c1db","value":"DBLP"}},{"alternateIdentifiers":[{"scheme":"doi","value":"10.1609/aaai.v39i11.33221"}],"type":"Conference object","urls":["https://dblp.org/rec/conf/aaai/GanianIT25.html","https://doi.org/10.1609/aaai.v39i11.33221"],"refereed":"nonPeerReviewed","hostedBy":{"key":"openaire____::d8b68cc0a53121f6f896883a7d60c1db","value":"DBLP"},"collectedFrom":{"key":"openaire____::d8b68cc0a53121f6f896883a7d60c1db","value":"DBLP"}}],"links":[{"header":{"relationType":"resultProject","relationClass":"isProducedBy","relatedIdentifier":"corda_____he::352a84fb7feeb560b967c83edda2bac5","relatedRecordType":"project","relationProvenance":"sysimport:crosswalk:repository","trust":"0.9"},"collectedfrom":[{"dsId":"openaire____::3f264f93cf3b0cfc4ede188a6300455c","dsName":"CORDA - COmmon Research DAta Warehouse - Horizon Europe"}],"projectTitle":"Efficient, portabLe And Secure orchesTration for reliable servICes","code":"101139067","funding":{"funder":{"id":"ec__________::EC","shortname":"EC","name":"European Commission","jurisdiction":{"code":"EU","label":"European Union"},"pid":null},"level0":{"id":"ec__________::EC::HE","description":"Horizon Europe Framework Programme","name":"HE"},"level1":{"id":"ec__________::EC::HE::HORIZON-JU-RIA","description":"HORIZON JU Research and Innovation Actions","name":"HORIZON-JU-RIA"},"level2":{"id":null,"description":null,"name":null}},"startDate":"2024-03-01","endDate":"2027-02-28"},{"header":{"relationType":"resultProject","relationClass":"isProducedBy","relatedIdentifier":"corda_____he::ca9d0ce42b3cb57bb6c93e1398f53ded","relatedRecordType":"project","relationProvenance":"sysimport:crosswalk:repository","trust":"0.9"},"collectedfrom":[{"dsId":"openaire____::3f264f93cf3b0cfc4ede188a6300455c","dsName":"CORDA - COmmon Research DAta Warehouse - Horizon Europe"}],"projectTitle":"Trustworthy and Resilient Decentralised Intelligence for Edge Systems","code":"101093006","funding":{"funder":{"id":"ec__________::EC","shortname":"EC","name":"European Commission","jurisdiction":{"code":"EU","label":"European Union"},"pid":null},"level0":{"id":"ec__________::EC::HE","description":"Horizon Europe Framework Programme","name":"HE"},"level1":{"id":"ec__________::EC::HE::HORIZON-RIA","description":"HORIZON  Research and Innovation Actions","name":"HORIZON-RIA"},"level2":{"id":null,"description":null,"name":null}},"startDate":"2023-01-01","endDate":"2026-03-31"}],"otherTitles":null,"inDiamondJournal":false,"green":true,"isGreen":true,"isInDiamondJournal":false}