Onlinealgoritmer

Onlinealgoritmer er algoritmer, der behandler input sekventielt, én del ad gangen, og træffer beslutninger uden at kende resten af inputtet på forhånd. Hver beslutning bygger på de oplysninger, der allerede er tilgængelige, og tidligere valg kan ikke ændres, når nyt input ankommer. Dette adskiller onlinealgoritmer fra offline algoritmer, der får fuld adgang til hele dataen samtidigt.

Konkurrenceanalyse er den mest udbredte evalueringsmetode for onlinealgoritmer. Den sammenligner algoritmens præstation med den optimale offline løsning, der kender hele inputtet fra starten. For deterministiske onlinealgoritmer gælder en generel målestok kaldet konkurrerende ratio, som beskriver hvor dårligt den online løsning kan være i værste fald. Randomiserede onlinealgoritmer kan have forventede konkurrerende ratioer under forskellige adversary-modeller, såsom en oblivious eller en adaptiv modstander.

Kendte onlineproblemer inkluderer caching (paging), hvor en algoritme skal beslutte hvilke sider der skal udskiftes, samt ski rental, k-server og online knapsack. Dette giver en ramme for at studere, hvordan beslutninger påvirker ressourcer som plads, tid og omkostninger uden fuld forudgående information.

Modeler og variationer: Onlinealgoritmer analyseres ofte under hostile input fra en adversary. Man skelner mellem oblivious og adaptive adversaries. Nogle varianter tillægger også ekstra information via rådgivning (advice) eller forskellige informationsstrømme.

Anvendelser findes i webcaching, belastningsbalancering, realtidsplanlægning og streaming, hvor beslutninger skal træffes, før alle data er kendt. Begrænsninger ved onlineanalyse omfatter potentielt dårlige worst-case præstationer og ofte konservative forventninger; i praksis kan hybrid- eller online-til offline-tilgange give bedre resultater.

Historien peger på, at konkurrerende analyse blev formaliseret i midten af 1980’erne af Sleator og Tarjan, der studerede paging og caching som grundlæggende eksempler.