I omordning bufferthanteringsproblem (RBM) en sekvens av n färgade objekt går in i en buffert med begränsad kapacitet k. När bufferten är full, tas ett objekt bort till utdatasekvensen, vilket ger utrymme för nästa inmatningsobjekt. Detta steg upprepas tills inmatningssekvensen är uttömd och bufferten är tom. Målet är att hitta en sekvens av borttagningar som minimerar det totala antalet färgförändringar i utdatasekvensen. Problemet formaliserar många tillämpningar i dator- och produktionssystem, och är känd för att vara NP-hård. Vi ger den första konstanta faktor approximation garanti för ringpärmsmekanismer. Vår algoritm är baserad på en invecklad "avrundning" av lösningen till en LP avslappning för RBM, så det etablerar också en konstant övre gräns på integrality gapet av denna avslappning. Våra resultat förbättras på den bästa tidigare gränsen av O( ε log k) av Adamaszek et al. (STOC 2011) som använde olika metoder och gav en online-algoritm. Vår konstanta faktor approximation slår de super-konstant lägre gränserna på konkurrensförhållandet ges av Adamaszek et al. Detta är den första demonstrationen av en offline-algoritm för RBM som är bevisligen bättre än någon online-algoritm.
Den offline algoritm av Avigdor-Elgrabli och Rabani REF bygger på en invecklad avrundning av en lösning av en LP-avslappning av problemet.
A Constant Factor Approximation Algorithm for Reordering Buffer Management
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}