2026-07-25T10:01:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20200 2024-07-02T07:52:51Z ddc:004 open_access

Non-Linear Paging Doron-Arad, Ilan Naor, Joseph (Seffi) paging competitive analysis non-linear paging submodular and supermodular functions We formulate and study non-linear paging - a broad model of online paging where the size of subsets of pages is determined by a monotone non-linear set function of the pages. This model captures the well-studied classic weighted paging and generalized paging problems, and also submodular and supermodular paging, studied here for the first time, that have a range of applications from virtual memory to machine learning. Unlike classic paging, the cache threshold parameter k does not yield good competitive ratios for non-linear paging. Instead, we introduce a novel parameter 𝓁 that generalizes the notion of cache size to the non-linear setting. We obtain a tight deterministic 𝓁-competitive algorithm for general non-linear paging and a o(log²𝓁)-competitive lower bound for randomized algorithms. Our algorithm is based on a new generic LP for the problem that captures both submodular and supermodular paging, in contrast to LPs used for submodular cover settings. We finally focus on the supermodular paging problem, which is a variant of online set cover and online submodular cover, where sets are repeatedly requested to be removed from the cover. We obtain polylogarithmic lower and upper bounds and an offline approximation algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ilan Doron-Arad and Joseph (Seffi) Naor 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.57 urn:nbn:de:0030-drops-202000 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.57 eng https://creativecommons.org/licenses/by/4.0/legalcode