I problemet med paketbuffertar online (även känt som den oviktade FIFO-varianten av bufferthantering) fokuserar vi på en enda nätverkspaketkopplingsenhet med flera ingångsportar och en utgångsport. Denna enhet vidarebefordrar enhetsstorlek, enhetsvärdepaket från ingångsportar till utgångsporten. Bufferter kopplade till inmatningsportar kan ackumulera inkommande paket för senare överföring; om de inte kan rymma alla inkommande paket, deras överskott förloras. En paketbuffert algoritm måste välja mellan vilka buffertar att överföra paket för att minimera antalet förlorade paket och därmed maximera genomströmningen. Vi presenterar en tight nedre gräns av e/(e − 1)  på konkurrensförhållandet av genomströmningsmaximering, som håller även för fraktionerade eller randomiserade algoritmer. Detta förbättrar den tidigare mest kända nedre gränsen på 1,4659 och matchar prestandan hos algoritmen RANDOM SCHEDULE. Vårt resultat motsäger den påstådda prestandan hos algoritmen RANDOM PERMUTATION; vi påpekar en brist i sin ursprungliga analys.
Bienkowski REF presenterar en lägre gräns för e/e − 1)  på konkurrensförhållandet för alla (även randomiserade) algoritmer.
An Optimal Lower Bound for Buffer Management in Multi-Queue Switches
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Mathematics', 'Computer Science']}