Vi anser online-algoritmer för den generaliserade caching problem. Här får vi en cache av storlek k och sidor med godtyckliga storlekar och hämta kostnader. Med tanke på en begäran sekvens av sidor, är målet att minimera den totala kostnaden för att hämta sidorna i cache. Vi ger en online-algoritm med konkurrensförhållande O(log 2 k), som är den första algoritmen för problemet med konkurrensförhållande sublinear i k. Vi ger också förbättrade O(log k)-konkurrenskraftiga algoritmer för specialfall av Bit Modell och Fel modell. I Bit Model, hämta kostnaden är proportionell mot storleken på sidan och i Felet modellen alla hämta kostnader är enhetliga. Tidigare var en O(log 2 k)-kompetitiv algoritm på grund av Irani [14] känd för båda dessa modeller. Våra algoritmer är baserade på en förlängning av det primära-dual ramverket för online-algoritmer som utvecklades av Buchbinder och Naor [7]. Vi skapar först en O (log k)-kompetitiv fraktionerad algoritm för problemet. Detta görs genom att använda en förstärkt LP formulering med knapsack-cover begränsningar, där exponentiellt många begränsningar läggs till vid ankomsten av en ny begäran. För det andra, vi runda online den fraktionerade lösningen och få en randomiserad online-algoritm. Våra tekniker ger ett enhetligt ramverk för cache-algoritmer och är betydligt enklare än de som tidigare använts.
Vår online-algoritm generaliserar O(log k)-kompetitiv algoritm för viktad caching REF, med hjälp av befintliga online LP lösare på ett svart-box mode.
Randomized competitive algorithms for generalized caching
{'venue': "STOC '08", 'journal': None, 'mag_field_of_study': ['Computer Science']}