Vi överväger problemet med sorteringsbuffertar. Input till detta problem är en sekvens av förfrågningar, var och en anges av en punkt i ett metriska utrymme. Det finns en "server" som går från punkt till punkt för att tjäna dessa önskemål. För att fylla i en begäran måste servern besöka den punkt som motsvarar den begäran. Målet är att minimera den totala sträcka som servern reser i det metriska utrymmet. För att uppnå detta, servern tillåts att tjäna förfrågningar i någon ordning som kräver att "buffer" som mest k förfrågningar när som helst. Således en giltig ombeställning kan tjäna en begäran endast efter att ha fyllt alla utom k tidigare förfrågningar. I detta dokument betraktar vi detta problem på linjen metrisk som motiveras av dess tillämpning på disk schemaläggning problem. Vi presenterar första approximationsalgoritmer med icke-triviala approximativa proportioner i både online- och offlineinställningar. På en linje med n jämnt fördelade punkter, ger vi en randomiserad online-algoritm med ett konkurrenskraftigt förhållande av O(log 2 n) i förväntan mot en glömsk motståndare. I offline-inställningen ger vår algoritm den första approximationen av konstantfaktorn och körs i kvasi-polynomtid N · n · k O(log n) där N är det totala antalet förfrågningar. Vårt tillvägagångssätt är baserat på ett dynamiskt program som håller reda på antalet pågående förfrågningar i vart och ett av O(log n) linjesegment som geometriskt ökar i längd.
Khandekar och Pandit REF ger en randomiserad O(log 2 n)-konkurrenskraftig online-algoritm för n jämnt fördelade punkter på en linje, och en konstant faktor offline approximation i kvasi-polynom tid.
Online and offline algorithms for the Sorting Buffers Problem on the line metric
{'venue': 'J. Discrete Algorithms', 'journal': 'J. Discrete Algorithms', 'mag_field_of_study': ['Mathematics', 'Computer Science']}