Hvis to passagerer bestiller billet til hhv. strækningen Odense-Slagelse og Ringsted-København, kan man vælge at placere de to passager på samme sæde eller på hver sit sæde. Kommer der senere en passager, som gerne vil rejse fra Nyborg til København, vil det være bedst, hvis man har placeret de to første passagerer på samme sæde. Kommer der derimod to passagerer, som gerne vil rejse hhv. fra Odense til Ringsted og fra Slagelse til København, vil det være bedst, hvis man har placeret de to første på hver sit sæde:
Algoritmer, som løser problemer, der som pladsreservationsproblemet har en online natur, kaldes online-algoritmer. Der findes forskellige online-algoritmer, som løser pladsreservationsproblemet. En af dem er First-Fit, som nummererer sæderne og placerer hver passager på det sæde med lavest nummer, som er ledigt på hele den ønskede strækning. I ovenstående eksempel ville First-Fit vælge at placere de to første passagerer på samme sæde, og dermed klare sig godt i det første scenario, men dårligt i det andet.
Eksemplet i foregående afsnit viser, at selv den bedste online-algoritme ikke altid kan levere den optimale løsning -- enhver algoritme er nødt til at placere de to første passagerer enten på det samme eller på hver sit sæde, og i begge tilfælde kan det senere gå galt. Men da problemet jo skal løses på en online facon, er det interessant at undersøge, hvor gode løsninger man kan forvente af en given online-algoritme. Til det formål virker det naturligt at sammenligne algoritmens resultat med det bedst mulige, der kunne opnås, hvis man havde kendt hele input på forhånd; dvs. at sammenligne algoritmen med en optimal offline-algoritme. Man kan vælge at se på, hvordan algoritmen i gennemsnit vil klare sig, men det kræver viden om, hvordan input fordeler sig. Ofte har man ikke en sådan viden, eller det kan være meget vanskeligt at regne på, og man vælger derfor at anlægge en pessimistisk synsvinkel: hvad er det værste der kan ske? Det er præcis, hvad man gør, når man anvender ``competitive analysis''; en algoritmes competitive ratio er groft sagt det største tal, man kan få når man dividerer værdien af den optimale offline løsning med værdien af algoritmens løsning. Competitive ratio er blevet standardmålet for kvaliteten af online-algoritmer. Det er dog ikke altid, competitive ratio kan bidrage med nyttig information. For pladsreservationsproblemet kan man f.eks. vise at enhver algoritme har en competitive ratio, som er proportional med antallet af stationer. Dvs. alle algoritmer har nogenlunde samme (meget dårlige) competitive ratio, så når vi skal beslutte os for, hvilken algoritme vi skal bruge, er competitive ratio ikke til meget hjælp.
Når man analyserer algoritmer, er man ofte ikke interesseret i et absolut mål for, hvor god en algoritme er; man vil blot vide hvilken af de algoritmer, man kan vælge imellem, der vil være bedst. Da kan det være smart at sammenligne algoritmerne direkte, idet det ser ud til, at information går tabt i den mellemliggende sammenligning med en optimal offline-algoritme, som foretages i competitive analyse. En første ide kunne være at sammenligne en online-algoritme med en anden online-algoritme på samme måde som man i competitive analyse sammenligner en online-algoritme med en optimal offline-algoritme. Problemet er, at så kommer man ofte ud for, at man får et tal, som er større end 1 for nogle input og mindre end 1 for andre, svarende til at i nogle situationer er den ene algoritme bedst, og i andre situationer er den anden bedst. Ofte er de input, som giver de største ratios, ret kunstige input, som giver nogle helt andre resultater, blot man ændrer lidt på rækkefølgen af reservationerne. Hvis alle rækkefølger er nogenlunde lige sandsynlige kan det være naturligt, for hver algoritme, at betragte den rækkefølge, som vil være værst for algoritmen.
Vores gruppe har for nylig introduceret relative worst order ratio, som netop sammenligner par af algoritmer direkte, og for hver algoritme og hvert sæt af reservationer betragter den permutation, som vil få algoritmen til at levere det dårligste resultat. Vi har anvendt dette kvalitetsmål på algoritmer til en række online problemer, hvor competitive ratio enten ikke giver nogen information eller giver resultater, som er i direkte modstrid med det, man observerer i praksis. Hver gang har relative worst order ratio givet mere information og information, som er i bedre overensstemmelse med praktisk erfaring, end de resultater, man opnår med competitive analyse.
Forbedringer i kvalitetsmålene for on-line algoritmer kan lede til forbedrede algoritmer og dermed nedsatte omkostninger for de dele erhvervslivet, der er afhængig af online problemer. Her kunne være tale om eksempelvis pakningsproblemer (f.eks. madvarer i kasser eller forsendelser i containere), skedulering af taxi, opskæring af materialer i forskellige mål, eller IT-relaterede problemer som skedulering af job på flere processorer og web caching.