2026-07-22T06:32:18Z https://drops.dagstuhl.de/oai

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

Caching Connections in Matchings Sadeh, Yaniv Kaplan, Haim Caching Matchings Caching in Matchings Edge Coloring Online Algorithms Motivated by the desire to utilize a limited number of configurable optical switches by recent advances in Software Defined Networks (SDNs), we define an online problem which we call the Caching in Matchings problem. This problem has a natural combinatorial structure and therefore may find additional applications in theory and practice. In the Caching in Matchings problem our cache consists of k matchings of connections between servers that form a bipartite graph. To cache a connection we insert it into one of the k matchings possibly evicting at most two other connections from this matching. This problem resembles the problem known as Connection Caching [Cohen et al., 2000], where we also cache connections but our only restriction is that they form a graph with bounded degree k. Our results show a somewhat surprising qualitative separation between the problems: The competitive ratio of any online algorithm for caching in matchings must depend on the size of the graph. Specifically, we give a deterministic O(nk) competitive and randomized O(n log k) competitive algorithms for caching in matchings, where n is the number of servers and k is the number of matchings. We also show that the competitive ratio of any deterministic algorithm is Ω(max(n/k,k)) and of any randomized algorithm is Ω(log (n/(k² log k)) ⋅ log k). In particular, the lower bound for randomized algorithms is Ω(log n) regardless of k, and can be as high as Ω(log² n) if k = n^{1/3}, for example. We also show that if we allow the algorithm to use at least 2k-1 matchings compared to k used by the optimum then we match the competitive ratios of connection catching which are independent of n. Interestingly, we also show that even a single extra matching for the algorithm allows to get substantially better bounds. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yaniv Sadeh and Haim Kaplan 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.120 urn:nbn:de:0030-drops-202639 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.120 eng https://creativecommons.org/licenses/by/4.0/legalcode