Menu

Online-algoritmer

Mange problemer fra den virkelige verden har et online præg; beslutninger skal tages løbende, inden alle data er kendt. Et eksempel er DSB's pladsreservation: Et tog har et vist antal pladser, som fordeles til de rejsende, efterhånden som de bestiller billetter. Nogle gange er man nødt til at afvise rejsende, som gerne vil have en pladsbillet, fordi der ikke længere er en plads, som er ledig på hele den ønskede strækning - også selv om man kunne have fået plads til alle, hvis man havde kunnet vente med at fordele pladserne, til alle bestillinger var modtaget. At beslutninger skal tages online lægger altså en begrænsning på, hvor gode løsninger, der kan opnås (dvs. hvor mange passagerer, man kan få plads til i et tog for eksempel). Men vælger man den rigtige algoritme (metode til at løse problemet), kan man ofte opnå gode løsninger alligevel.

 

Når man skal afgøre, hvor god en online-algoritme er, er det praktisk at have et teoretisk værktøj til at vurdere kvaliteten af algoritmen. Standard-værktøjet, competitive analyse, har desværre vist sig mangelfuldt for mange vigtige online-problemer, og der er derfor behov for alternativer og supplementer. Dette er fokus for vores gruppe. Vi har bl.a. udviklet kvalitetsmålet relative worst-order ratio, som har vist sig at supplere competitive analyse rigtig godt. Ofte får man langt mere information, når man anvender dette mål frem for competitive ratio. Vigtige eksempler på dette er bin packing og paging.

 

En af gruppens seneste aktiviteter omhandler advice complexity af forskellige online-problemer. Advice complexity er et mål for mængden af information, det er nødvendigt at have på forhånd for at opnå en bestemt performance. Gruppen har brugt advice complexity til at definere de første kompleksitetsklasser for online-problemer.

 

Gruppen har bl.a. arbejdet med følgende problemer: pladsreservation, bin packing, paging, TCP acknowledgment, graffarvning og diverse planlægningsproblemer, herunder opdeling af store BLAST jobs, som ankommer online.

 

Gruppen har kontakter til mange andre institutioner, bl.a. ETH, University of Haifa, Universitetet i Bergen, University of California - Irvine, University of Toronto, University of Leicester og University of Waterloo.

 

Videnskabelige medarbejdere

Joan Boyar 
Lene Monrad Favrholdt 
Kim Skak Larsen 

                                                                                                                                                                        

 

Vi samler statistik ved hjælp af cookies for at forbedre brugeroplevelsen.  Læs mere om cookies

Acceptér cookies