I problemet med bufferthantering med begränsad fördröjning, paket med vikter och deadlines anländer till ett nätverk switch över tid, och målet är att skicka dessa paket på utgående länken samtidigt maximera den totala vikten av paket som skickas före deras deadlines. Vi presenterar en studie av randomiserade algoritmer som är konkurrenskraftiga mot en adaptiv motståndare. Tidigare studier betraktade endast den omedvetna motståndaren modell som inte fångar beroendet av nätverkstrafik på paketet schemaläggning algoritm. Vi ger en ny analys av en tidigare känd algoritm, som visar att den fortfarande är e/(e-1)-konkurrenskraftig även mot en adaptiv motståndare. Vi kompletterar detta med en 4/3 lägre gräns på konkurrensförhållandet på 2-bundna instanser, där varje paket har en livslängd på ett eller två steg. Vi studerar också mer begränsade 2-uniforma fall, där varje paket har en livslängd på exakt två steg. För sådana fall ger vi en 1,2 lägre gräns på konkurrensförhållandet mellan godtyckliga algoritmer och 4/3 lägre gräns på konkurrensförhållandet mellan minneslösa skal-invarianta algoritmer. Slutligen utformar vi en 4/3-kompetitiv minneslös skal-invariant algoritm för 2-bundna instanser, som matchar två av dessa nedre gränser.
En förfinad analys visar dock att RMIX fortfarande är 1,582-kompetitivt i den adaptiva motståndaremodellen REF.
Randomized competitive algorithms for online buffer management in the adaptive adversary model
{'venue': 'Theor. Comput. Sci.', 'journal': 'Theor. Comput. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}