V sprotnem načinu se elementi razkrivajo eden za drugim in odločitev o akciji je potrebno sprejeti preden pride naslednji element. Raziskave usmerjamo v sprotne algoritme z nasveti, v katerih se omejeno vedenje o prihodnjih zahtevah uporablja za izboljšanje konkurenčnega razmerja. Preučujemo dvodimenzionalni problem pakiranja vektorjev, posplošitev znanega problema pakiranja košev, ki je NP-težak. Izziv je najti najmanjše število dvodimenzionalnih košev, v katere je mogoče zapakirati zaporedje dvodimenzionalnih vektorjev, ne da bi presegli kapaciteto katerega koli koša v kateri koli dimenziji. Prikazujemo spodnjo mejo~$(5D+12)/10$ za konkurenčno razmerje katere koli strategije pakiranja vektorjev \textsc{AnyFit} za D-dimenzionalni problem, kar pomeni~$11/5$ za $D=2$.
Prikazujemo tudi zgornje meje med $2$ in $5/2$, odvisno od omejitev kota vektorjev ob logaritemsko velikem nasvetu. Trenutno najboljša konkurenčna strategija ima konkurenčno razmerje $27/10$, brez uporabe nasvetov.
|
