Abstrakt. En accepterad åtgärd för prestanda hos en online-algoritm är det "konkurrensförhållande" som införts av Sleator och Tarjan. Denna åtgärd är väl motiverad och har lett till utvecklingen av en matematisk teori för online-algoritmer. Vi undersöker beteendet hos denna åtgärd med avseende på minnesbehov och fördelar med lookahead och hitta några kontraintuitiva funktioner. Vi presenterar lägre gränser för storleken på minnet som ägnas åt att spela in det förflutna. Det noteras också att konkurrensförhållandet inte återspeglar någon förbättring av prestandan för en online-algoritm på grund av någon (fin) mängd lookahead. Vi erbjuder en alternativ åtgärd som uppvisar ett annat och i vissa avseenden mer intuitivt beteende. I synnerhet visar vi användningen av vår nya åtgärd genom att analysera avvägningen mellan den amorterade kostnaden för online-algoritmer för personsökning problem och mängden lookahead tillgängliga för dem. Vi härleder också on-line algoritmer för K-server problem på alla avgränsade metriska utrymme, som, i förhållande till den nya åtgärden, är optimala bland alla on-line algoritmer (upp till en faktor på 2) och ligger inom en faktor på 2K från den optimala off-line prestanda.
När det gäller förhållandet Max/Max visade REF att algoritmen k-Center är asymptotiskt optimal upp till en faktor på 2 bland alla online-algoritmer och upp till en faktor på 2k från den optimala offline-algoritmen.
A new measure for the study of on-line algorithms
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Computer Science']}