dc_1179_16
Online algoritmusok versenyk´epess´egi elemz´ese MTA doktora disszert´aci´o t´ezisf¨ uzete
Imreh Csan´ ad Informatika Int´ezet, Szegedi Tudom´ anyegyetem Szeged
2016
Powered by TCPDF (www.tcpdf.org)
dc_1179_16
1.
Online algoritmusok
A gyakorlati probl´em´ akban gyakran fordulnak el˝o olyan optimaliz´ al´ asi feladatok, ahol az inputot csak r´eszenk´ent ismerj¨ uk meg, ´es a d¨ ont´eseinket a m´ ar megkapott inform´ aci´ ok alapj´an, a tov´abbi adatok ismerete n´elk¨ ul kell meghoznunk. Ilyen feladatok eset´en online probl´em´ ar´ ol besz´el¨ unk. Az online algoritmusok elm´elet´enek igen sok alkalmaz´ asa van a sz´ am´ıt´ astudom´ any, az oper´aci´okutat´as ´es a k¨ ozgazdas´ agtan k¨ ul¨ onb¨ oz˝ o ter¨ uletein. Az els˝ o eredm´enyek az online algoritmusok elm´elet´enek ter¨ ulet´er˝ ol az 1970-es ´evekb˝ ol sz´ armaznak, majd a 90-es ´evek elej´et˝ol kezdve egyre t¨ obb kutat´ o kezdett el az online algoritmusok ter¨ ulet´ehez kapcsol´ od´ o probl´em´ akkal foglalkozni. Sz´ amos r´eszter¨ ulet alakult ki ´es napjainkban is a legfontosabb, algoritmusokkal foglalkoz´o konferenci´ akon rendszeresen ismertetnek u ´j eredm´enyeket ezen t´emak¨orb˝ol. Mivel egy online algoritmusnak r´eszenk´ent kell meghozni a d¨ont´eseit a teljes input ismerete n´elk¨ ul, ez´ert egy ilyen algoritmust´ol nem v´ arhatjuk el, hogy a teljes inform´ aci´ oval rendelkez˝o algoritmusok ´ altal megkaphat´ o optim´ alis megold´ ast szolg´altassa. Azon algoritmusokat, amelyek ismerik a teljes inputot offline algoritmusoknak nevezz¨ uk. Az online algoritmusok hat´ekonys´ ag´ anak vizsg´alat´ara k´et alapvet˝ o m´ odszert haszn´ alnak. Az egyik lehet˝ os´eg az ´atlagos eset elemz´ese. Ebben az esetben fel kell t´etelezn¨ unk valamilyen val´osz´ın˝ us´egi eloszl´ ast a lehets´eges inputok ter´en, ´es az erre az eloszl´asra vonatkoz´ o v´ arhat´ o ´ert´ek´et vizsg´ aljuk a c´elf¨ uggv´enynek. Ezen megk¨ozel´ıt´es h´ atr´ anya, hogy ´ altal´ aban nincs inform´ aci´ onk arr´ol, hogy a lehets´eges inputok milyen val´ osz´ın˝ us´egi eloszl´ ast k¨ ovetnek. Mi a disszert´aci´oban az ´ atlagos eset elemz´es´enek t´emak¨ or´evel nem foglalkozunk, hanem az elterjedtebb versenyk´epess´egi anal´ızis m´odszer´et haszn´aljuk. A m´ asik megk¨ ozel´ıt´es egy legrosszabb-eset korl´at elemz´es, amelyet versenyk´epess´egi elemz´esnek nevez¨ unk. Ebben az esetben az online algoritmus ´ altal kapott megold´ as c´elf¨ uggv´eny´ert´ek´et hasonl´ıtjuk ossze az optim´ ¨ alis offline c´elf¨ uggv´eny´ert´ekkel. Egy online minimaliz´ al´ asi probl´ema eset´en egy online algoritmust C-versenyk´epesnek nevez¨ unk, ha tetsz˝ oleges inputra teljes¨ ul, hogy az algoritmus ´ altal kapott megold´ as k¨ olts´ege nem nagyobb, mint Cszer az optim´ alis offline k¨ olts´eg. Egy algoritmus versenyk´epess´egi h´ anyadosa a legkisebb olyan C sz´ am, amelyre az algoritmus C-
1
Powered by TCPDF (www.tcpdf.org)
dc_1179_16
versenyk´epes. ´ Altal´ aban egy tetsz˝ oleges ALG online algoritmusra az I inputon felvett c´elf¨ uggv´eny´ert´eket ALG(I)-vel jel¨ olj¨ uk. Az I inputon felvett optim´ alis offline c´elf¨ uggv´eny´ert´eket OPT(I)-vel jel¨olj¨ uk. Haszn´alva ezt a jel¨ ol´esrendszert a fent defini´ alt versenyk´epess´eget minimaliz´al´asi probl´em´ akra a k¨ ovetkez˝ ok´eppen adhatjuk meg. Az ALG algoritmus C-versenyk´epes ha ALG(I) ≤ C · OPT(I) teljes¨ ul minden I input eset´en. Szok´ asos haszn´ alni a versenyk´epess´eg egy tov´abbi v´altozat´at. Egy minimaliz´ al´ asi probl´ema eset´en az ALG algoritmus aszimptotikusan C-versenyk´epes, ha van olyan B konstans, hogy ALG(I) ≤ C · OPT(I) + B teljes¨ ul minden I input eset´en. Egy algoritmus aszimptotikus versenyk´epess´egi h´ anyadosa a legkisebb olyan C sz´am, amelyre az algoritmus aszimptotikusan C-versenyk´epes. Fontosnak tartjuk megjegyezni, hogy a fenti fogalomra n´eha haszn´ alj´ ak a gyenge versenyk´epess´eg kifejez´est is, illetve sok esetben ezt nevezik versenyk´epess´egnek ´es az addit´ıv konstanst nem megenged˝o fogalmat pedig abszol´ ut versenyk´epess´egnek. A aszimptotikus ver∞ senyk´epess´egi h´ anyadost (RALG ) t¨ obb l´ adapakol´asi dolgozatban a k¨ ovetkez˝ o formul´ akkal defini´ alj´ ak. n RALG = max{ALG(I)/OPT(I) | OPT(I) = n} ∞ n RALG = lim sup RALG . n→∞
A disszert´ aci´ oban (´es sz´ amos egy´eb dolgozatban) haszn´alt addit´ıv konstanst megenged˝ o defin´ıci´ o nem ekvivalens a lim sup f¨ uggv´eny alapj´ an kapott defin´ıci´ oval, ez ut´ obbi p´eld´aul az addit´ıv konstans helyett megenged tetsz˝ oleges o(OP T (I)) nagys´ag´ u addit´ıv f¨ uggv´enyt is. M´ asr´eszt a legt¨ obb esetben, ´es a dolgozatban bemutatott eredm´enyekn´el is, az addit´ıv tag konstans, ´ıgy mindk´et defin´ıci´o szerint ugyanazt az aszimptotikus versenyk´epess´egi h´anyadost kapjuk. Az aszimptotikus h´ anyados f˝ o tulajdons´ aga az, hogy azt vizsg´alja, mik´ent viselkedik az algoritmus akkor, ha az optimum ´ert´eke nagy, azaz ha az optim´ alis k¨ olts´eg v´egtelenhez tart. Ez ´altal´aban azt jelenti, hogy az algoritmus szabadon d¨ onthet az input kezdeti r´eszein´el. A fentiekben a minimaliz´ al´ asi probl´em´ akra defini´altuk a versenyk´epess´egi anal´ızis fogalmait. A defin´ıci´ ok hasonl´oan ´ertelmezhet˝oek
2
Powered by TCPDF (www.tcpdf.org)
dc_1179_16
maximaliz´ al´ asi probl´em´ ak eset´en is. Ekkor az ALG algoritmus Cversenyk´epes ha C · ALG(I) ≥ OPT(I) teljes¨ ul minden I input eset´en, illetve aszimptotikusan C-versenyk´epes ha valamely B konstans mellett C · ALG(I) + B ≥ OPT(I) teljes¨ ul minden I inputra. Sz´ amos tudom´ anyos dolgozat vizsg´ al v´eletlen´ıtett online algoritmusokat. Ebben az esetben az algoritmus v´eletlen d¨ont´eseket is hoz, ´ıgy az ´ altala kapott c´elf¨ uggv´eny´ert´ek egy val´ osz´ın˝ us´egi v´altoz´o, ´es a versenyk´epess´egi h´ anyados defin´ıci´ oj´ aban ezen val´osz´ın˝ us´egi v´altoz´o v´ arhat´ o ´ert´eke szerepel. Mivel a disszert´ aci´ oban csak determinisztikus online algoritmusokkal fogunk foglalkozni, ez´ert a v´eletlen´ıtett algoritmusokra vonatkoz´ o fogalmakat nem r´eszletezz¨ uk. A disszert´ aci´ oban h´ arom r´eszter¨ ulettel foglalkozunk. Els˝ok´ent a g´epk¨ olts´eges u ¨temez´esi probl´em´ akra el´ert eredm´enyeinket mutatjuk be, majd k¨ ul¨ onb¨ oz˝ o l´ adapakol´ asi ´es l´ adafed´esi modellekkel foglalkozunk. V´eg¨ ul az online klaszterez´es ter¨ ulet´en el´ert eredm´enyeket ismertetj¨ uk.
2.
Online u ¨ temez´ es g´ epk¨ olts´ eggel
A legelterjedtebb online u ¨temez´esi modell a lista modell, ahol adott m darab azonos g´ep ´es amelyben a munk´ ak egy list´ar´ol ´erkeznek. Amikor egy munk´ at megkapunk a list´ ar´ ol, akkor ismerj¨ uk meg az elv´egz´es´ehez sz¨ uks´eges v´egrehajt´ asi id˝ ot, ´es ezt k¨ovet˝oen u ¨temezn¨ unk kell a munk´ at valamely g´epen hozz´ arendelve a kezd´esi ´es befejez´esi id˝ ot, amelyeket k´es˝ obb m´ ar nem v´ altoztathatunk meg, ´es csak ezt k¨ ovet˝ oen kapjuk meg a list´ ar´ ol a k¨ ovetkez˝ o munk´at. A legsz´elesebb k¨ orben vizsg´ alt c´elf¨ uggv´eny a maxim´ alis befejez´esi id˝o minimaliz´al´ asa. Ebben az esetben (mik´ent a probl´ema offline v´altozat´aban is) elegend˝ o olyan algoritmusokkal foglalkoznunk, amelyek nem hagynak u ¨res id˝ ointervallumokat a g´epeken, azaz amelyekben az egyes g´epeken a munk´ ak sz¨ unet n´elk¨ ul k¨ ovetik egym´ast. Ekkor minden g´epre a maxim´ alis befejez´esi id˝ o megegyezik a g´ephez rendelt munk´ak v´egrehajt´ asi idejeinek ¨ osszeg´evel. A g´epen lev˝ o munk´ak v´egrehajt´asi idejeinek ¨ osszeg´et a g´epen lev˝ o t¨ olt´esnek h´ıvjuk. Teh´at ebben az esetben elegend˝ o csak azt megmondani, hogy az adott munk´at, melyik g´ephez rendelj¨ uk, ´es a c´el a maxim´ alis t¨ olt´es minimaliz´al´asa. Ez az egyik els˝ o online probl´ema, ami publik´ al´asra ker¨ ult. A [21] cikkben a Lista algoritmust elemezt´ek, amely az aktu´alis munk´at
3
Powered by TCPDF (www.tcpdf.org)
dc_1179_16
mindig ahhoz a g´ephez rendeli, ahol a t¨ olt´es minim´alis. Az algoritmus versenyk´epess´egi h´ anyadosa 2 − 1/m. ¨ Utemez´ esi feladatok eset´en ´ altal´ aban a g´epek sz´ama adott param´etere a feladatnak. Ugyanakkor sz´ amos alkalmaz´as eset´en a g´epek sz´ ama megv´ altoztathat´ o. Az ilyen probl´em´ak vizsg´alhat´oak a g´epk¨ olts´eges modellben, amit a [27] cikk¨ unkben vezett¨ unk be. Ebben a modellben a g´epek sz´ ama nem adott, hanem az algoritmusnak meg kell v´ as´ arolnia azokat, ´es a c´el a g´epek v´as´arl´as´ara k¨olt¨ott k¨ olts´eg ´es a maxim´ alis befejez´esi id˝ o (ami ebben a modellben megegyezik a maxim´ alis t¨ olt´essel) ¨ osszeg´enek a minimaliz´al´asa. A [27] cikkben a g´epk¨ olts´eges feladatokra a k¨ ovetkez˝o algoritmusoszt´alyt vizsg´ altuk meg. Egy tetsz˝ oleges n¨ ovekv˝ o % = (0 = %1 , %2 , . . . , %i . . . ) sorozatra defini´ alhatjuk a k¨ ovetkez˝ o A% algoritmust. Amikor a j` munka meg´erkezik A% annyi g´epet v´ as´ arol (ha sz¨ uks´eges), hogy a g´epek i sz´ ama teljes´ıtse a %i ≤ P < %i+1 egyenl˝otlens´eget, ahol P az eddig meg´erkezett munk´ ak v´egrehajt´ asi idejeinek az ¨osszege. Az A% algoritmus a fentiekben eml´ıtett Lista algoritmus alapj´an u ¨temezi a munk´ akat, az esetleges g´epv´ as´ arl´ ast k¨ ovet˝oen hozz´arendeli az aktu´ alis munk´ at ahhoz a g´ephez, ahol a t¨ olt´es minim´alis. A [27] cikket k¨ ovet˝ oen sz´ amos eredm´enyt publik´altak a probl´ema ´es annak k¨ ul¨ onb¨ oz˝ o v´ altozatainak megold´ as´ ara, de a [26] cikket megel˝ oz˝ oen ezek mindegyike felt´etelezte, hogy a g´epek v´as´arl´asi k¨olts´ege minden g´epre megegyezik. Ebben a cikkben egy ´altal´anosabb modellt vizsg´ altunk, ahol a g´epek k¨ olts´eg´et egy c monoton nemcs¨okken˝o k¨ olts´egf¨ uggv´eny ´ırja le. Ekkor c(i) az els˝ o i darab g´ep megv´as´arl´as´anak k¨ olts´eg´et adja meg, azaz az i-dik g´ep ´ ara c(i)−c(i−i), a c(0) = 0 ´ert´eket haszn´ alva. Ebben az ´ altal´ anos modellben is vizsg´altuk az A% algoritmusokat ´es az al´ abbi eredm´enyeket kaptuk. 1. T´ etel. ([26]) Ha % = (0, c(2)ϕ, 2c(3)ϕ, . . . , (i − 1)c(i)ϕ, . . . ), akkor az A% algoritmus 1 + ϕ ≈ 2.618-versenyk´epes, ahol ϕ = (1 + √ 5)/2. 2. T´ etel. ([26]) Ha % = (0, c(2), 2c(3), . . . , (i−1)c(i), . . . ) ´es minden munka m´erete legfeljebb maxi {c(i)−c(i−1)} akkor az A% algoritmus versenyk´epess´egi h´ anyadosa 2. Az al´ abbi als´ o korl´ at, amit a lehets´eges versenyk´epess´egi h´anyadosokra igazoltunk mutatja, hogy a kis munk´ ak eset´en siker¨ ult optim´ alis versenyk´epess´eg˝ u algoritmust tal´ alnunk. 4
Powered by TCPDF (www.tcpdf.org)
dc_1179_16
3. T´ etel. ([26]) Van olyan c k¨ olts´egf¨ uggv´eny, amelyre az ´ altal´ anos k¨ olts´eg˝ u g´epk¨ olts´eges u ¨temez´esi feladatra nincs olyan online algoritmus, amelynek kisebb a versenyk´epess´egi h´ anyadosa, mint 2. Az als´ o korl´ at fenn´ all olyan speci´ alis esetre is, ahol minden munka m´erete legfeljebb maxi {c(i) − c(i − 1)}. Szint´en megvizsg´ altunk egy olyan v´ altozatot is, ahol a g´epeknek k¨ ul¨ onb¨ oz˝ o sebess´egei lehetnek. Ekkor a munka megadott v´egrehajt´ asi idej´et osztani kell a g´ep sebess´eg´evel ´es ´ıgy kapjuk meg az adott g´epen megjelen˝ o t¨ olt´est. A vizsg´ alt g´epk¨ olts´eges v´altozatban k´et g´ephalmazunk van, S1 olyan g´epeket tartalmaz, amelyek sebess´ege 1, ´es S2 olyan g´epeket, amelyek sebess´ege s > 1. Az algoritmus mindk´et halmazb´ ol v´ as´ arolhat g´epeket. Az S1 halmaz g´epeinek k¨ olts´eg´et egy c1 nemcs¨ okken˝ o f¨ uggv´eny ´ırja le (c1 (k) a halmaz els˝o k g´ep´enek megv´ as´ arl´ asi k¨ olts´ege) ´es az S2 halmaz g´epeinek k¨olts´eg´et egy c2 nemcs¨ okken˝ o f¨ uggv´eny ´ırja le (c2 (k) a halmaz els˝o k g´ep´enek megv´ as´ arl´ asi k¨ olts´ege). A c´elf¨ uggv´eny itt is, a g´epek v´as´arl´as´ara k¨ olt¨ ott ¨ osszegnek ´es a maxim´ alis befejez´esi id˝ onek az ¨osszeg´enek a minimaliz´ al´ asa. A k¨ ovetkez˝ o GRM (Greedy for Related Machines) algoritmusnak vizsg´ altuk a versenyk´epess´eg´et. Az algoritmus minden l´ep´esben haszn´ alja az OP T` ´ert´eket, ami az els˝ o ` munk´ab´ol ´all´o input optim´ alis megold´ as´ anak k¨ olts´ege. Amikor egy u ´j j` munka ´erkezik a GRM algoritmus annyi g´epet vesz (amennyiben sz¨ uks´eges), hogy a g´epek i1 , i2 sz´ am´ ara a k´et oszt´ alyban teljes¨ ulj¨ on c1 (i1 ) ≤ OP T` < c1 (i1 + 1) ´es c2 (i2 ) ≤ OP T` < c2 (i2 + 1). Ezt k¨ovet˝oen az algoritmus a munk´ at a Lista algoritmus k¨ ul¨ onb¨ oz˝ o g´epekre vonatkoz´o kiterjeszt´ese alapj´ an u ¨temezi, arra a g´epre rakja, ahol a munka u ¨temez´es´et k¨ ovet˝ oen a t¨ olt´es minim´ alis lesz. Ha t¨ obb ilyen g´ep is van, akkor a gyorsabb g´epek k¨ oz¨ ul v´ alasztja a legkisebb index˝ ut. Az algoritmus versenyk´epess´eg´et a k¨ ovetkez˝ o t´etel adja meg. 4. T´ etel. [26] A GRM algoritmus versenyk´epess´egi h´ anyadosa 6. Fontos megeml´ıteni, hogy OP T` meghat´ aroz´asa egy NP-neh´ez feladat, ´ıgy az algoritmusunk fut´ asi ideje exponenci´alis. M´asr´eszt az optim´ alis megold´ as ´ert´eke helyett haszn´ alhatunk egy approxim´aci´os algoritmus vagy approxim´ aci´ os s´ema ´ altal kapott ´ert´eket is, csak akkor a versenyk´epess´egi h´ anyados is n¨ ovekszik (c-approxim´aci´os algoritmus eset´en 4 + 2c-re). 5
Powered by TCPDF (www.tcpdf.org)
dc_1179_16
K¨ ul¨ on vizsg´ altuk azt a probl´em´ at is, amelyben mindk´et halmazban adott a g´epek sz´ ama, ´es csak u ¨temezni kell a munk´akat. Ez felfoghat´ ou ´gy is, hogy a g´epek v´ as´ arl´ asi f¨ uggv´enye olyan, hogy az egyes halmazokb´ ol k illetve m g´epet ingyen megkapunk, a t¨obbiek´ert pedig egy v´egtelen nagy ¨ osszeget kell fizetni. Ebben az esetben a GRM algoritmus 4-versenyk´epes, ´es megadtunk egy, a [25] cikk¨ unkben kor´ abban ismertetett algoritmus tov´ abbfejleszt´es´en alapul´o 3versenyk´epes algoritmust is. Az [12] cikkben egy m´ as ir´ any´ u kiterjeszt´es´evel foglalkoztunk a g´epk¨ olts´eges u ¨temez´esi feladatnak. Ezt az u ¨temez´esi probl´em´at geometriai ´ertelemben felfoghatjuk u ´gy is, hogy egys´eg ´es v´egrehajt´asi id˝ o oldalakkal rendelkez˝ o t´eglalapokat kell elhelyezn¨ unk a g´epek altal kijel¨ ´ olt s´ avokban minimaliz´ alva a g´epek sz´am´anak ´es a felhaszn´ alt s´ avok maxim´ alis hossz´ anak az ¨ osszeg´et. Ennek a folytonos v´ altozata az, hogy a t´eglalapokat tetsz˝ olegesen helyezhetj¨ uk el egy befoglal´ o t´eglalapban, a befoglal´ o t´eglalap oldalainak ¨osszeg´enek minimaliz´ al´ as´ aval. Pontosabban egy ´ altal´ anosabb γH+W c´elf¨ uggv´enyt vizsg´ altunk, ahol H a befoglal´ o t´eglalap magass´aga, W a befoglal´ o t´eglalap sz´eless´ege, γ > 0 pedig a feladat egy param´etere. A probl´ema azt az a´ltal´ anos er˝ oforr´ as allok´ aci´ os modellt ´ırja le, ahol az inputk´ent ´erkez˝ o t´eglalapok sz´eless´ege a feladat v´egrehajt´ashoz sz¨ uks´eges er˝ oforr´ as mennyis´eg´et, a magass´ aga pedig a v´egrehajt´ashoz sz¨ uks´eges id˝ ot adja meg. A befoglal´ o t´eglalap oldalai pedig a teljes sorozat v´egrehajt´ as´ ahoz egy id˝ oben ig´enybe vett maxim´alis er˝oforr´as mennyis´eg´et ´es a v´egrehajt´ ashoz sz¨ uks´eges id˝ ot adj´ak meg. Ezek s´ ulyozott ¨ osszege a minimaliz´ aland´ o c´elf¨ uggv´eny. Az online v´altozatban a t´eglalapok egyenk´ent j¨ onnek, ´es minden t´eglalapot a tov´abbi t´eglalapokra vonatkoz´ o inform´ aci´ ok n´elk¨ ul kell elhelyezn¨ unk az eddigiekkel val´ o´ atfed´es n´elk¨ ul a s´ıkon. A befoglal´ o t´eglalap a legkisebb olyan t´eglalap lesz, ami minden lerakott kis t´eglalapot tartalmaz az inputb´ ol. Amennyiben a befoglal´ o t´eglalap egyik oldal´anak a m´erete r¨ogz´ıtett, akkor a probl´ema u ´gy fogalmazhat´ o meg, hogy egy adott sz´eless´eg˝ u s´ avba kell pakolnunk ´ atfed´es ´es forgat´as n´elk¨ ul t´eglalapokat, a felhaszn´ alt r´esz magass´ ag´ at minimaliz´ alva. Ezt a s´avpakol´asi feladatot, amit a l´ adapakol´ asi probl´ema k´etdimenzi´os kiterjeszt´esek´ent is lehet defini´ alni t¨ obb tanulm´ anyban is vizsg´alt´ak. A jelenleg ismert legjobb algoritmusok 6.623-versenyk´epesek, ilyen algoritmusokat publik´ altak [23] ´es [33] cikkekben. T¨obb cikkben is pub6
Powered by TCPDF (www.tcpdf.org)
dc_1179_16
lik´ altak egyre nagyobb als´ o korl´ atokat a lehets´eges versenyk´epess´egi h´ anyadosra, a jelenlegi legnagyobb als´ o korl´ at 2.589, amit a [22] cikkben igazoltak. Aszimptotikus versenyk´epess´eg szempontj´ab´ol az el´erhet˝ o legkisebb aszimptotikus versenyk´epess´egi h´anyados h∞ ≈ 1.69103, amit egy, a [10] cikkben bemutatott polcpakol´asi algoritmus ´er el. A polcpakol´ asi algoritmusok l´enyege, hogy v´ızszintes r´eszs´ avokat (polcokat) hozunk l´etre a befoglal´o s´avon bel¨ ul ´es az aktu´ alis t´eglalapot mindig valamelyik polcra helyezz¨ uk el. Az ´ altalunk vizsg´ alt ´ altal´ anosabb t´eglalap pakol´asi probl´em´ara a k¨ ovetkez˝ o polcpakol´ asi algoritmust fejlesztett¨ uk ki. A Shelf(α) algoritmus az ´erkez˝ o t´eglalapokra els˝ ok´ent mindig meghat´arozza azok t´ıpus´ at. Egy pi = (wi , hi ) m´eret˝ u t´eglalap ´erkez´ese eset´en ez az a k sz´ am lesz, melyre a 2k−1 < hi ≤ 2k egyenl˝otlens´eg teljes¨ ul. Ezt k¨ ovet˝ oen, ha van nyitott k t´ıpus´ u (2k magas) polc, akkor rakjuk a t´eglalapot erre a polcra annyira balra, amennyire lehets´eges. Amennyiben, ezt k¨ ovet˝ oen a polcon felhaszn´ alt sz´eless´eg el´eri a befoglal´ o t´eglalap aktu´ alis magass´ ag´ anak α-szoros´at z´arjuk le a polcot. Ha pedig nincs nyitott k t´ıpus´ u polc (m´eg egy´ altal´an nem hoztunk ilyet l´etre vagy az utols´ o k t´ıpus´ u t´eglalapn´ al lez´artuk a k t´ıpus´ u polcot), akkor hozzunk l´etre egy ilyen polcot a meglev˝o polcok tetej´en, ´es rakjuk a t´eglalapot a polc bal sark´ aba. Amennyiben, ezt k¨ovet˝oen a polcon felhaszn´ alt sz´eless´eg el´eri a befoglal´ o t´eglalap aktu´alis magass´ ag´ anak α-szoros´ at z´ arjuk le a polcot. Az algoritmus versenyk´epess´eg´ere vonatkozik az al´abbi t´etel. q p 5. T´ etel. [12] A Shelf(α) algoritmus 4 αγ + αγ + 4 + αγ -verp senyk´epes. Ha u ´gy v´ alasztjuk meg az α param´etert, hogy α/γ = 0.46161 teljes¨ ulj¨ on, akkor az algoritmus 7.4803-versenyk´epes. Szint´en megvizsg´ altuk azt a f´elig-online esetet, ahol el˝ore tudjuk, hogy a t´eglalapok cs¨ okken˝ o magass´ ag szerinti sorrendben ´erkeznek. Ez a tulajdons´ ag nagym´ert´ekben k¨ onnyebb´e teszi a feladat megold´ as´ at, mik´ent azt a k¨ ovetkez˝ o algoritmus mutatja. A SDH(β) algoritmus az els˝ o t´eglalaphoz defini´ al egy polcot, amelynek a magass´ aga ezen t´eglalap magass´ aga, ´es amely bal sark´aban ez a t´eglalap van. Ez a polc lesz az aktu´ alis polc. A tov´ abbi t´eglalapokat az al´ abbi szab´ aly szerint pakoljuk. Ha a sz´eless´ege az aktu´alis polcnak legfeljebb β-szor akkora, mint az aktu´ alis magass´aga a befoglal´o t´eglalapnak, akkor rakjuk a t´eglalapot erre a polcra annyira balra, 7
Powered by TCPDF (www.tcpdf.org)
dc_1179_16
amennyire lehets´eges. Ellenkez˝ o esetben z´ arjuk be az aktu´alis polcot, amit nem fogunk t¨ obbet haszn´ alni. Nyissunk egy u ´j polcot az eddigi polcok tetej´en, legyen a magass´ aga az aktu´alisan elpakoland´o t´eglalap magass´ aga ´es rakjuk a t´eglalapot az u ´j polc bal sark´aba. Ezen algoritmus versenyk´epess´eg´ere vonatkozik az al´abbi ´all´ıt´as. 6. T´ etel. [12] A SDH(β) algoritmus 2.5-versenyk´epes, amennyiben β = 0.6γ. Sz´ amos gyakorlati probl´em´ aban fordul el˝ o, hogy egy elv´egzend˝o feladat eset´en sem az ahhoz rendelt er˝ oforr´ as mennyis´ege sem pedig a v´egrehajt´ as ideje nem r¨ ogz´ıtett, hanem megtehetj¨ uk azt, hogy n¨ ovelve a haszn´ alt er˝ oforr´ as mennyis´eg´et cs¨ okkentj¨ uk a v´egrehajt´asi id˝ ot vagy cs¨ okkentve a felhaszn´ alt er˝ oforr´ as mennyis´eg´et n¨ovelj¨ uk a v´egrehajt´ asi id˝ ot. A s´ avpakol´ asi probl´em´ akban ez u ´gy ´ırhat´o le, hogy a t´eglalapok m´erete megv´ altoztathat´ o. Egy ilyen v´altozat´at az online s´ avpakol´ asi probl´em´ anak, ahol a t´eglalapok megny´ ujthat´oak a ter¨ ulet fixen hagy´ asa mellett, vizsg´ altunk a [24] dolgozatban. Ezeket az eredm´enyeket nem tartalmazza a disszert´aci´o. A disszert´aci´ oban a v´ altoztathat´ o t´eglalapok eset´et az ´ altal´anosabb modellre vizsg´ altuk, ahol a befoglal´ o t´eglalap egyik oldala sem r¨ogz´ıtett. Ekkor a t´eglalapnak az inputban csak a ter¨ ulet´et kapjuk meg, az algoritmusnak kell eld¨ ontenie azt, hogy milyen form´aj´ u t´eglalapot szeretne elpakolni a befoglal´ o t´eglalapba. A m´ odos´ıthat´ o m´eret˝ u t´eglalapok eset´ere, a γ = 1 esetben a k¨ ovetkez˝ o Expand(1) algoritmust fejlesztett¨ uk ki, amely alap¨otlete, hogy megpr´ ob´ al n´egyzethez min´el hasonl´ obb befoglal´o t´eglalapot l´etrehozni. Ha a k-adik t´eglalap ter¨ ulet´et T (k), a k-adik t´eglalap ´erkez´es´et megel˝ oz˝ oen a befoglal´ o t´eglalap oldalait A(k) ≤ B(k) jel¨olik, akkor a k-adik t´eglalap a(k), b(k) oldalait ´es az elhelyezked´es´et az al´ abbi szab´ alyokkal adhatjuk meg. • Ha a k¨ ovetkez˝ o t´eglalap kicsi, azaz T (k) ≤ B(k)2 , akkor le(k) ≤ B(k). Majd ragasszuk gyen b(k) = B(k) ´es a(k) = Tb(k) az ´ıgy kapott t´eglalapot a nagyobbik oldal´aval a befoglal´o t´eglalaphoz, azaz legyen B(k + 1) = max {B(k), A(k) + a(k)} ´es A(k + 1) = min {B(k), A(k) + a(k)}. • Ha a k¨ ovetkez˝ op t´eglalap nagy, azaz T (k) > B(k)2 , akkor legyen a(k) = b(k) = T (k). Majd ragasszuk az ´ıgy kapott n´egyzetet 8
Powered by TCPDF (www.tcpdf.org)
dc_1179_16
a befoglal´ o t´eglalap nagyobbik oldal´ ahoz, azaz legyen A(k + 1) = a(k) and B(k + 1) = A(k) + a(k). Az ´ altal´ anos γ eset´et visszavezett¨ uk a γ = 1 speci´alis esetre, az igazi t´eglalapok ´es igazi befoglal´ o t´eglalap helyett m´odos´ıtott virtu´ alis t´eglalapokat haszn´ alva. Az ´ıgy kapott Expand(γ) algoritmus versenyk´epess´eg´ere vonatkozik az al´ abbi ´all´ıt´as. √
7. T´ etel. [12] Az Expand(γ) algoritmus
3.
21 4
≈ 1.1456-versenyk´epes.
L´ adapakol´ asi ´ es fed´ esi probl´ em´ ak
A l´ adapakol´ asi probl´em´ aban inputk´ent t´ argyak egy sorozat´at kapjuk meg, ahol az i-edik t´ argyat a m´erete hat´ arozza meg, ami egy si ∈ (0, 1] ´ert´ek. C´elunk a t´ argyak elhelyez´ese a lehet˝o legkevesebb egys´eg m´eret˝ u l´ ad´ aba. Form´ alisabban megfogalmazva a t´argyakat minim´ alis sz´ am´ u olyan csoportba akarjuk P sz´etosztani, hogy minden csoportra a benne lev˝ o t´ argyakra a si ≤ 1 felt´etel teljes¨ ulj¨on. A feladat online v´ altozat´ aban a t´ argyak egyenk´ent ´erkeznek ´es az aktu´ alis t´ argyat a tov´ abbi t´ argyakra vonatkoz´ o inform´aci´ok n´elk¨ ul kell elhelyezn¨ unk valamely l´ ad´ aba. Egy l´ ad´ ara a benne lev˝o t´argyak m´ereteinek ¨ osszeg´et a l´ ada t¨ olt´es´enek h´ıvjuk. Az online l´ adapakol´ asra ´es v´ altozataira sz´ amos algoritmust fejlesztettek ki. Ezen algoritmusok elemz´es´ere t¨ obbnyire az aszimptotikus versenyk´epess´egi h´ anyadost haszn´ alj´ ak. Az algoritmusok egy nagy oszt´ alya a fit t´ıpus´ u algoritmusokat tartalmazza, amelyek csak akkor nyitnak u ´j l´ ad´ at, ha az aktu´ alis t´argy egyetlen nyitott l´ ad´ aba sem f´er el. T¨ obb algoritmus ker¨ ult kifejleszt´esre att´ol f¨ ugg˝ oen, hogy a haszn´ alhat´ o l´ ad´ ak k¨ oz¨ ul melyiket v´alasztjuk. A k´et legismertebb ilyen algoritmus a k¨ ovetkez˝ o. A FF algoritmus soha nem z´ ar be l´ ad´ akat ´es az aktu´ alis t´ argyhoz az els˝o olyan l´ad´at v´ alasztja, amelybe a t´ argy belef´er. A NF algoritmus pedig mindig csak egy l´ ad´ at tart nyitva, ´es ha abban az aktu´alis t´argy nem f´er el, akkor a l´ ad´ at bez´ arja ´es egy u ´j l´ ad´ at nyit a t´argynak. Egy m´ asik nagy oszt´ alya az algoritmusoknak a harmonic t´ıpus´ u algoritmusok oszt´ alya, ahol a t´ argyakat m´eret szerint online oszt´alyozzuk ´es a k¨ ul¨ onb¨ oz˝ o oszt´ alyokat k¨ ul¨ on l´ adahalmazokba pakoljuk. A legkisebb aszimptotikus versenyk´epess´eggel a [30] cikkben publik´alt algoritmus rendelkezik, amely 1.58889-versenyk´epes. A probl´ema de9
Powered by TCPDF (www.tcpdf.org)
dc_1179_16
fini´ al´ asa ´ ota t¨ obbsz¨ or jav´ıtott´ ak a versenyk´epess´egre vonatkoz´o als´o korl´ atokat, a jelenlegi legjobb korl´ at 248/161 ≈ 1.54037, amit a [5] cikkben publik´ altak. A l´ adafed´esi feladat a l´ adapakol´ asi feladat du´alisa. Az inputot ugyan´ ugy a t´ argyak m´eretei adj´ ak, de a c´elunk most a maxim´alis sz´ am´ u egys´egl´ ada lefed´ese. Azaz a t´ argyakat a maxim´alis sz´am´ u olyan csoportba szeretn´enk csoportos´ıtani, ahol minden csoportban legal´ abb 1 a t´ argyak ¨ osszege. A feladatot a [2] cikkben kezdt´ek el vizsg´ alni, ahol igazolt´ ak, hogy az online NF algoritmus, ami a t´ argyakat addig rakja az aktu´ alis l´ ad´ aba, am´ıg le nem fedi ´es csak ut´ ana nyit u ´j l´ ad´ at, 2-versenyk´epes. Ez a korl´ at egyb˝ol ad´odik mivel minden l´ ad´ aban a t¨ olt´es legfeljebb 2. A cikkben offline approxim´ aci´ os algoritmusokat is vizsg´ altak egy 23 ´es egy 34 approxim´aci´os algoritmust adtak meg. K´es˝ obb a [9] cikkben igazol´ast nyert, hogy nem adhat´ o meg olyan online algoritmus a l´ adafed´esi probl´em´ara, amelynek az aszimptotikus versenyk´epess´ege kisebb, mint 2. A klasszikus l´ adapakol´ asi feladatban nagyon kicsi a r´es az als´o ´es fels˝ o korl´ atok k¨ oz¨ ott, a l´ adafed´es eset´en pedig ismert a legkisebb versenyk´epess´eg˝ u algoritmus. A kutat´ asok f˝ oleg k¨ ul¨onb¨oz˝o v´altozatok illetve kiterjeszt´esek ter¨ ulet´en folynak. Mi a disszert´aci´oban korl´atozott l´ adapakol´ asi ´es l´ adafed´esi feladatokkal foglalkoztunk, ahol a l´ ada tartalm´ ara a kapacit´ as´ an k´ıv¨ ul tov´ abbi korl´atok is vannak. Ezeket az eredm´enyeket foglaljuk ¨ ossze a k¨ ovetkez˝okben. Majd egy olyan l´ adafed´esi v´ altozattal foglalkozunk, ahol a l´ad´ak sz´ama adott ´es a c´el a haszn´ alt t´ argyak m´ereteinek ¨ osszeg´enek minimaliz´al´asa.
3.1.
Sz´ınkorl´ atos l´ adapakol´ as
A sz´ınkorl´ atos l´ adapakol´ asi feladatban, a t´ argyaknak nem csak m´erete van, hanem minden t´ argynak adott egy ci sz´ıne is ´es adott egy k sz´ am. A l´ ad´ ak tartalm´ ara a m´eretek ¨ osszeg´ere vonatkoz´o korl´aton k´ıv¨ ul m´eg teljes¨ ulnie kell annak is, hogy a t´ argyak legfeljebb k k¨ ul¨ onb¨ oz˝ o sz´ınoszt´ alyba tartoznak. Az online probl´em´at els˝ok´ent a [31, 32] cikkekben vizsg´ alt´ ak, ahol k´et first fit (ff) t´ıpus´ u algoritmus elemeztek. Az els˝ o ff-nek nevezett algoritmus egy t´argy ´erkez´esekor az els˝ o olyan l´ ad´ aba pakolja azt, ahol nem s´erti sem a m´eretekre sem a sz´ınek sz´ am´ ara vonatkoz´ o korl´atot. Ha nincs ilyen l´ ada, akkor az algoritmus u ´j l´ ad´ at nyit a t´ argynak. A m´asik vizsg´alt elj´ ar´ as a (csff) (color sets first fit) algoritmus. Ebben az al10
Powered by TCPDF (www.tcpdf.org)
dc_1179_16
goritmusban a sz´ıneket online csoportos´ıtjuk k elem˝ u halmazokba, az els˝ ok´ent megjelent k sz´ın tartozik az els˝ o csoportba, ut´ana mindig a m´eg nem l´ atott k¨ ovetkez˝ o k sz´ın alkotja a k¨ovetkez˝o csoportot. Minden sz´ınoszt´ alyra k¨ ul¨ on l´ adahalmazokon futtatjuk a ff algoritmust. A [31] cikkben azt a speci´ alis esetet vizsg´alt´ak, ahol minden t´ argy m´erete ugyanakkora. Igazolt´ ak, hogy mind a csff mind pedig a ff algoritmus aszimptotikus versenyk´epess´ege 2. Az ´altal´anos esetet, ahol k¨ ul¨ onb¨ oz˝ o m´eret˝ uek lehetnek a t´ argyak a [32] cikkben vizsg´ alt´ ak. Itt egy, a t´ argyak m´eret szerinti oszt´alyoz´as´an alapul´o algoritmust elemeztek, amely aszimptotikusan 2.75-versenyk´epes. Ha minden t´ argy sz´ıne k¨ ul¨ onb¨ oz˝ o, akkor a sz´ınekre vonatkoz´o korl´at arra reduk´ al´ odik, hogy minden l´ ad´ aba legfeljebb k darab t´argyat lehet rakni. Ezt a modellt elemsz´ amkorl´ atos l´adapakol´asi feladatnak nevezik, ´es t¨ obb tanulm´ any is foglalkozott az online ´es offline probl´em´ aval, r´eszletek tal´ alhat´ oak a [4, 14] cikkekben ´es az ott szerepl˝ o hivatkoz´ asokban. A probl´em´ at a [16] cikkben tov´ abb vizsg´ altuk, ezeket az eredem´enyeket foglaljuk ¨ ossze az al´ abbiakban. Tov´abb elemezt¨ uk a csff algoritmust az ´ altal´ anos m´eret˝ u t´ argyak eset´ere ´es az al´abbi eredm´enyt igazoltuk. 8. T´ etel. ([16]) A csff algoritmus aszimptotikusan (2 + senyk´epes a sz´ınkorl´ atos l´ adapakol´ asi feladatra.
k−1 k )-ver-
Tov´ abb´ a kifejlesztett¨ unk egy m´ odszert, amely seg´ıts´eg´evel a l´adapakol´ asi algoritmusok egy sz´eles oszt´ alya transzform´alhat´o az ´altal´ anosabb, sz´ınoszt´ alyokkal rendelkez˝ o feladatra a versenyk´epess´egi h´ anyados n¨ ovel´ese mellett. Ehhez defini´ altuk az uniform pakol´ asi algoritmusok fogalm´at. Legyen A egy olyan, egy t eg´esz param´etert˝ ol f¨ ugg˝o l´adapakol´asi al1 goritmus, amely sz´etosztja a t´ argyakat kicsi (a (0, t+1 ] intervallumba es˝ o m´eret˝ u) ´es nagy (a t¨ obbiek) t´ argyakra, ahol a nagy t´argyak esetleg tov´ abbi r´eszhalmazokra oszthat´ ok. Az algoritmust, akkor nevezz¨ uk uniformnak, ha a nagy t´ argyakat a kis t´argyakt´ol f¨ uggetlen¨ ul pakolja egy k¨ ul¨ on l´ adahalmazba, a kis t´ argyakat pedig a nf algoritmus szerint. Egy ilyen algoritmust a k¨ ovetkez˝ ok´eppen terjeszthet¨ unk ki a sz´ınkorl´ atos pakol´ asi probl´ema megold´ as´ ara. A nagy t´argyakat az A algoritmusnak megfelel˝ oen pakoljuk. Mivel minden t´argy nagyobb, 1 mint t+1 ez´ert legfeljebb t ilyen t´ argyat tartalmaznak a l´ad´ak. Ha 11
Powered by TCPDF (www.tcpdf.org)
dc_1179_16
t ≤ k, akkor ezek a l´ ad´ ak biztosan kiel´eg´ıtik a sz´ınek sz´am´ara vonatkoz´ o korl´ atokat. A kis t´ argyakat pedig a nf algoritmus helyett annak a csnf kiterjeszt´es´evel pakoljuk, ami a csff algoritmusn´al haszn´alt m´ odon sz´ın szerinti csoportokat pakol diszjunkt l´adahalmazokba, csak nem a ff hanem a nf algoritmus szerint. Ezt az algoritmust cs(A)-val jel¨ olj¨ uk. A kiterjeszt´es csak kism´ert´ekben n¨oveli a versenyk´epess´egi h´ anyadost, amint ezt az al´ abbi ´all´ıt´as mutatja. 9. T´ etel. ([16]) Legyen R egy fels˝ o korl´ at egy A uniform algoritmus aszimptotikus versenyk´epess´egi h´ anyados´ ara a klasszikus l´ adapakol´ as eset´en. Ekkor a cs(A) algoritmus aszimptotikusan R + 1 versenyk´epes a sz´ınkorl´ atos l´ adapakol´ asi feladatra. Nagy k eset´en a fenti t´etelt haszn´ alva ismert uniform algoritmusokra, kisebb k-ra pedig egy u ´j, a t´ argyak part´ıci´oj´an alapul´o algoritmust fejlesztve igazoltuk az al´ abbi ´ all´ıt´ ast. 10. T´ etel. ([16]) Minden k ´ert´ek eset´en l´etezik egy aszimptotikusan legfeljebb 2.63492-versenyk´epes algoritmus a sz´ınkorl´ atos l´ adapakol´ asi feladatra. Az al´ abbi als´ o korl´ atot is igazoltuk, a lehets´eges versenyk´epess´egi h´ anyadosra. 11. T´ etel. ([16]) Tetsz˝ oleges online algoritmusnak a sz´ınkorl´ atos l´ adapakol´ asi feladatra az aszimptotikus versenyk´epess´egi h´ anyadosa legal´ abb 1.5652. A korl´ at m´ ar a k = 2 esetben teljes¨ ul.
3.2.
Sz´ınkorl´ atos l´ adalefed´ es
A sz´ınkorl´ atos l´ adalefed´es a sz´ınkorl´ atos l´ adapakol´as du´alisa. Itt is minden t´ argyhoz egy m´eret ´es egy sz´ın van rendelve ´es adott egy k param´eter a feladatban. Egy sz´ınkorl´ atos l´ adafed´esen a t´argyak egy olyan csoportos´ıt´ as´ at (l´ ad´ akhoz rendel´es´et) ´ertj¨ uk, ahol minden csoportra teljes¨ ul, hogy a benne lev˝ o t´ argyak m´ereteinek ¨osszege legal´ abb 1 ´es az is, hogy a l´ ada legal´ abb k k¨ ul¨ onb¨oz˝o sz´ınoszt´alyb´ol tartalmaz t´ argyakat. A c´elunk egy olyan csoportos´ıt´as megtal´al´asa, ahol a csoportok sz´ ama maxim´ alis. Erre a probl´em´ara mi ´ert¨ uk el az els˝ o eredm´enyeket a [17] dolgozatban. A probl´ema egy speci´ alis eset´et vizsg´ altuk, ahol minden t´argynak ugyanakkora a m´erete. Ebben az esetben a probl´ema le´ırhat´o k´et 12
Powered by TCPDF (www.tcpdf.org)
dc_1179_16
pozit´ıv eg´esz sz´ ammal B-vel ´es k-val. Egy l´ ada akkor lesz lefedve, ha legal´ abb B t´ argyat rakunk a l´ ad´ aba ´es ezek a t´argyak legal´abb k k¨ ul¨ onb¨ oz˝ o sz´ınoszt´ alyhoz tartoznak. Ez azokat az eseteket ´ırja le, ahol a t´ argyak egys´eges m´erete az [1/B, 1/(B − 1)) intervallumba esik. Feltehetj¨ uk, hogy B ≥ k, hisz B < k eset´en nem v´altoztat a probl´em´ an, ha B ´ert´ek´et k-ra n¨ ovelj¨ uk. A probl´ema megold´ as´ ara els˝ ok´ent FF t´ıpus´ u algoritmusokat vizsg´ altunk. Az ff(1) algoritmus az al´ abbi m´ odon pakolja a t´argyakat. Mikor egy u ´j t´ argy ´erkezik a c sz´ınoszt´ alyb´ ol, akkor azt az els˝o olyan l´ ad´ ahoz rendelj¨ uk, amelynek a lefed´es´ehez hozz´a tud j´arulni. Ez azt jelenti, hogy az els˝ o olyan l´ ad´ at v´ alasztjuk ami kevesebb, mint B t´ argyat tartalmaz, vagy legal´ abb B t´ argyat tartalmaz, de az t´argyak kevesebb, mint k sz´ınoszt´ alyb´ ol ker¨ ulnek ki ´es nincs c-beli t´argy a l´ ad´ aban. Ha nincs ilyen l´ ada, akkor egy u ´j l´ ad´ at nyitunk az t´argynak. Az algoritmus hat´ekonys´ ag´ at az al´ abbi t´etel hat´arozza meg. 12. T´ etel. ([17]) Az ff(1) algoritmus aszimptotikus versenyk´epess´egi h´ anyadosa B + k − 1 minden k ≥ 2 ´es B ´ert´ekre. Az ff(2) algoritmus az ff(1) egy olyan tov´abbfejleszt´ese, ami azt is figyelembe veszi, hogy ha egy l´ ad´ aban m´ar vannak t´argyak de hi´ anyzik t ≤ k − 1 sz´ın a lefed´eshez, akkor ez a t extra t´argy hozz´ aj´ arul a m´eret szerinti lefed´eshez is. Teh´ at, ha egy l´ad´aban k − t sz´ınoszt´ alyb´ ol B − t t´ argy van, akkor az olyan tov´abbi t´argyak, amelyek m´ ar a l´ ad´ aban szerepl˝ o sz´ınoszt´ alyokhoz tartoznak val´oj´aban nem ny´ ujtanak seg´ıts´eget a l´ ada lefed´es´ehez. Mindezek alapj´an azt mondjuk, hogy egy t´ argynak egy m´eg nem lefedett l´ad´ahoz val´o hozz´ arendel´ese akkor hasznos, ha a l´ ad´ aban m´eg nincs ilyen sz´ın˝ u t´ argy, vagy ha van ilyen sz´ın˝ u t´ argy, ´es a l´ ad´ab´ol m´eg hi´anyz´o sz´ınoszt´ alyok sz´ ama kisebb, mint a l´ ad´ ab´ ol hi´ anyz´o t´argyak sz´ama. Haszn´ alva ezt a fogalmat az ff(2) algoritmus u ´gy defini´alhat´o, hogy az aktu´ alis t´ argyat az els˝ o olyan l´ ad´ aba teszi, amelyhez hasznos a hozz´ arendel´ese, ha nincs ilyen akkor pedig u ´j l´ ad´at nyit. Az algoritmus versenyk´epess´eg´et adja meg az al´ abbi t´etel. 13. T´ etel. ([17]) Az ff(2) algoritmus aszimptotikus versenyk´epess´egi h´ anyadosa B minden k ≥ 2 eset´en. Kifejlesztett¨ unk egy tov´ abbi algoritmust is. A Color&Size algoritmus alap¨ otlete az, hogy online m´ odon csoportos´ıtja a t´argyakat 13
Powered by TCPDF (www.tcpdf.org)
dc_1179_16
C t´ıpus´ u (sz´ınez˝ o) ´es S t´ıpus´ u (t¨ olt´esn¨ ovel˝ o) t´ argyakra. Az egyes csoportokat egy ff algoritmus szerint pakoljuk, de egym´ast´ol f¨ uggetlen¨ ul csak a sz´ıneket illetve csak a l´ ad´ ak t¨ olt´es´et figyelembe v´eve. Teh´ at egy S t´ıpus´ u t´ argyat az els˝ o olyan l´ ad´ aba rakunk, amelyben kevesebb, mint B darab S t´ıpus´ u t´ argy van, ha nincs ilyen akkor u ´j l´ ad´ at nyitunk. Egy C t´ıpus´ u t´ argyat pedig az els˝o olyan l´ad´aba rakunk, ahol m´eg nincs az adott sz´ınb˝ ol C t´ıpus´ u t´argy ´es ahol legfeljebb k − 1 k¨ ul¨ onb¨ oz˝ o sz´ınb˝ ol v´ alasztottunk m´eg C t´ıpus´ u t´argyat. Ha nincs ilyen l´ ada, akkor u ´j l´ ad´ at nyitunk. Az algoritmus pontos specifik´ aci´ oj´ ahoz meg kell m´eg adnunk, hogy milyen szab´ aly szerint csoportos´ıtjuk a t´ argyakat. Az algoritmus egy p eg´esz param´etert haszn´ al a csoportos´ıt´as sor´an. Tegy¨ uk fel, hogy a j-edik t´ argy ´erkezik, ´es ennek a t´ argynak a sz´ıne az i-edik fajta sz´ın, ami megjelent a sorozatban. Ekkor ha i mod p 6= 0 ´es j mod p 6= 0, akkor ez a t´ argy C t´ıpus´ u lesz, tov´ abbb´a ha i mod p = 0 ´es j mod p 6= 1 akkor is C t´ıpus´ u lesz a t´ argy. A tov´abbi esetekben pedig S t´ıpus´ u. Az algoritmus versenyk´epess´eg´et adja meg az al´abbi ´all´ıt´as. 14. T´ etel. ([17]) A Color&Size algoritmus aszimptotikusan O(k)versenyk´epes megfelel˝ o p param´eter v´ alaszt´ asa eset´en (az addit´ıv konstans is O(k)). Szint´en igazoltunk egy als´ o korl´ atot a lehets´eges versenyk´epess´egi h´ anyadosokra. Ezt adja meg az al´ abbi t´etel. 15. T´ etel. ([17]) Minden online algoritmusra teljes¨ ul, hogy az aszimptotikus versenyk´epess´egi h´ anyadosa legal´ abb 1 + Hk−1 = Ω(log k), Pk ahol Hk = i=1 1/i.
3.3.
Elemsz´ amkorl´ atos l´ adafed´ es
A [18] cikkben az elemsz´ amkorl´ atos l´ adafed´esi probl´em´at vizsg´altuk. Ebben a modellben a t´ argyak m´erete mellett adott egy k sz´am is, amit elemsz´ amkorl´ atnak nevez¨ unk. Egy l´ ad´ at akkor tekint¨ unk lefedettnek, ha a benne lev˝ o t´ argyak m´ereteinek ¨ osszege legal´abb 1, ´es legal´ abb k t´ argyat helyezt¨ unk el a l´ ad´ aba. A probl´ema speci´alis esete a fentiekben t´ argyalt sz´ınkorl´ atos l´ adafed´esi modellnek, ha minden t´ argy sz´ıne k¨ ul¨ onb¨ oz˝ o, akkor a sz´ınkorl´ atos modell az elemsz´amkorl´ atos modellre reduk´ al´ odik. A probl´ema szint´en speci´alis esete a 14
Powered by TCPDF (www.tcpdf.org)
dc_1179_16
vektorfed´esi feladatnak ([1]), ahol d-dimenzi´ os vektorokat kell csoportos´ıtanunk maxim´ alis sz´ am´ u csoportba u ´gy, hogy minden csoportban az oda rendelt vektorokra minden koordin´at´aban legal´abb 1 legyen az ¨ osszeg. Ha az egyik koordin´ at´ aban a t´argy m´eret´et adjuk meg, a m´ asikban pedig 1/k-t, akkor ez a k´et-dimenzi´os vektorfed´esi feladat az elemsz´ amkorl´ atos l´ adafed´esre reduk´al´odik. ´Igy a k´etdimenzi´ os vektorfed´esb˝ ol automatikusan ad´odik egy 4-versenyk´epes algoritmus, ez´ert csak ann´ al kisebb versenyk´epess´eg˝ u algoritmusok az ´erdekesek. A k¨ ovetkez˝ o Classify algoritmust fejlesztett¨ uk ki a probl´ema megold´ as´ ara. Ez az algoritmus egy α param´etert haszn´al, melyre 1 eret szerinti intervallumokra 2 ≤ α < 1. A (0, 1] intervallumot m´ osztjuk, ahol az intervallumok Ii = (αi+1 , αi ] alak´ uak. Azt mondjuk egy j t´ argy a Ci oszt´ alyba tartozik, ha a m´erete az Ii intervallumba esik. Az algoritmus haszn´ al k´et, k-t´ ol f¨ ugg˝ o 0 < q1 < q2 pozit´ıv eg´esz param´etert. Minden t´ argy vagy A vagy B t´ıpus´ u. Rendre jel¨olje niA ´es niB az eddig meg´erkezett A ´es B t´ıpus´ u t´ argyak sz´ am´ at a Ci oszt´alyb´ol. Ha az aktu´ alis t´ argy eset´en (niA + niB mod q2 ) < q2 − q1 , akkor a t´argy t´ıpusa B lesz, egy´ebk´ent (amennyiben (niA +niB mod q2 ) ≥ q2 −q1 ) a t´ argy t´ıpusa A. Az algoritmus u ´gy pakolja a t´ argyakat, hogy minden lefedett l´ ada pontosan (k − 2) darab B t´ıpus´ u t´argyat tartalmaz ´es legal´ abb 2 darab A t´ıpus´ u t´ argyat, amelyek m´ereteinek ¨osszege nagyobb, mint 1. Egy olyan l´ ad´ at, ami m´ ar tartalmaz (k − 2) darab B t´ıpus´ u t´ argyat, B szerint telinek nevez¨ unk. Egy olyan l´ad´at, amelyben az A t´ıpus´ u t´ argyak m´erete szigor´ uan nagyobb, mint 1 pedig A szerint telinek nevez¨ unk. Az´ert haszn´ alunk szigor´ uan nagyobb felt´etelt, mert ez garant´ alja, hogy legal´ abb k´et darab A t´ıpus´ u t´argyat fog tartalmazni a l´ ada. Nyilv´ an, ha egy l´ ada A ´es B szerint is teli, akkor az m´ ar fedett. Az algoritmus a FF elj´ ar´ ast haszn´alja az egyes t´ıpusokra egym´ ast´ ol f¨ uggetlen¨ ul. Teh´ at egy A t´ıpus´ u t´argy a legels˝o olyan l´ ad´ aba ker¨ ul, ami A szerint nincsen teli, egy B t´ıpus´ u t´argy a legels˝ o olyan l´ ad´ aba, ami B szerint nincsen teli. Az algoritmus versenyk´epess´eg´ere az al´ abbi ´all´ıt´ast igazoltuk 16. T´ etel. ([18]) Minden ε > 0 eset´en l´etezik olyan α ´ert´ek, hogy a q1 = 2k ´es q2 = 3k − 2 ´ert´ekv´ alaszt´ as mellett a Classify algoritmus . aszimptotikus versenyk´epess´ege legfeljebb 3k−2+ε k 15
Powered by TCPDF (www.tcpdf.org)
dc_1179_16
A dolgozatban szint´en igazoltuk az al´ abbi als´o korl´atot a lehets´eges versenyk´epess´egi h´ anyadosra. 17. T´ etel. ([18]) Minden k ≥ 4 eset´en teljes¨ ul, hogy nincs olyan online algoritmus az elemsz´ amkorl´ atos l´ adapakol´ asi feladatra, amelynek az aszimptotikus versenyk´epess´egi h´ anyadosa kisebb, mint 5k−4 2k . Megjegyezz¨ uk, hogy a disszert´ aci´ oban (´es a [18] cikkben is) vizsg´ altuk a probl´ema f´elig-online eset´et is, ahol felt´etelezt¨ uk, hogy a t´ argyak m´eret szerint monoton nemn¨ ovekv˝ o sorrendben ´erkeznek. Ebben az esetben siker¨ ult egy a Classify algoritmushoz hasonl´o elven m˝ uk¨ od˝ o aszimptotikusan 2-versenyk´epes algoritmust kifejleszteni ´es igazolni azt is, hogy enn´el kisebb versenyk´epess´egi h´anyadossal nem rendelkezik algoritmus.
3.4.
Online l´ adafed´ es a haszn´ alt t´ argyak o ¨sszs´ uly´ at minimaliz´ alva
A [7] cikkben a l´ adafed´es al´ abbi v´ altozat´ at vizsg´ altuk. Adott t´argyak egy online list´ aja, ´es adott m darab egys´eg m´eret˝ u l´ada. Feladatunk ezen l´ ad´ ak lefed´ese a t´ argyak list´ aj´ anak minim´alis ¨osszs´ uly´ u kezd˝ oszelet´evel. A feladat online, azaz a t´ argyak egyenk´ent ´erkeznek ´es az adott t´ argyat a tov´ abbi t´ argyakra vonatkoz´o ismeretek n´elk¨ ul kell egy l´ ad´ aba helyezn¨ unk. Az elj´ ar´ as akkor ´er v´eget ha mind az m l´ ad´ at lefedt¨ uk. Mivel a t´ argyak m´erete legfeljebb 1, ez´ert ha egy algoritmus egy lefedett l´ ad´ aba nem rak m´ ar tov´ abbi t´argyakat, akkor az az elj´ ar´ as v´eg´en minden l´ ad´ ahoz legfeljebb 2 mennyis´eg˝ u t´argyat rendel. Ebb˝ ol ad´ odik, hogy minden ilyen algoritmus 2-versenyk´epes, ´ıgy enn´el kisebb versenyk´epess´eggel rendelkez˝ o elj´ ar´ast kerest¨ unk. Fontos kiemeln¨ unk, hogy az offline algoritmusnak is a t´argyak list´aj´anak egy kezd˝ oszelet´et kell haszn´ alnia, az offline algoritmus sem rendezheti ´ at a t´ argyak sorrendj´et. Az ´ altalunk felvetett probl´ema du´ alis´ anak tekinthet˝o l´adapakol´asi probl´em´ at vizsg´ alt´ ak a [3] dolgozatban. Ott a c´el a l´ad´akba elhelyezhet˝ o t´ argyak sz´ am´ anak maximaliz´ al´ asa volt. Vizsg´alt´ak azt az ´ altalunk tekintett modellt, ahol a t´ argyak list´aj´anak maxim´alis kezd˝ oszelet´et kellett elpakolni, ´es azt is, ahol a t´argyak visszautas´ıthat´ oak voltak. A [3] cikkben el´ert eredm´enyek ´altal´anos m´eret˝ u l´ ad´ akra vonatkoz´ o kiterjeszt´es´et a [15] dolgozatban mutatt´ak be.
16
Powered by TCPDF (www.tcpdf.org)
dc_1179_16
K¨ ul¨ on vizsg´ altuk az m = 2 esetet. Ebben az esetben az aszimptotikus versenyk´epess´egnek nincs ´ertelme, hiszen a k´et l´ada lefed´es´ehez mindig elegend˝ o konstans, legfeljebb 4 ¨ osszm´eret˝ u t´argy. Ebben az m = 2 esetben a parametrikus v´ altozatot is vizsg´altuk, azaz azt az esetet, ha ki van k¨ otve, hogy a t´ argyak m´erete legfeljebb 1 lehet valamely p eg´ e szre. A p = 1 eset felel meg az ´altal´anos p probl´em´ anak. Az ´ altal´ anos g´epsz´ am eset´en m´ar az aszimptotikus h´ anyadost haszn´ altuk, hiszen ekkor egy m-t˝ ol f¨ uggetlen addit´ıv konstans nem oldja meg a feladatot, de seg´ıt az algoritmus kezdeti l´ep´eseiben. 3.4.1.
Az m = 2 eset
K´et l´ ada eset´ere a k¨ ovetkez˝ o TwoBins algoritmust dolgoztuk ki. Az algoritmus le´ır´ as´ ahoz jel¨ olje A1 ≥ A2 a l´ ad´akban lev˝o t¨olt´est (feltessz¨ uk, hogy A2 < 1, mivel ellenkez˝ o esetben m´ar le lenn´enek feddve a l´ ad´ ak). Az u ´j j t´ argyat a k¨ ovetkez˝ o szab´alyok szerint helyezz¨ uk el. Ha a t´ argy sj m´eret´ere 1 ≤ A2 + sj ≤ 2p+2 ul, 2p+1 teljes¨ akkor j-t az A2 t¨ olt´es˝ u l´ ad´ aba helyezz¨ uk el. Egy´ebk´ent ha A1 < 1 ´es A1 + sj ≤ 2p+2 olt´es˝ u l´ad´aba helyezz¨ uk el. 2p+1 , akkor j-t az A1 t¨ V´eg¨ ul, ha egyik felt´etel sem teljes¨ ul, akkor j-t az A2 t¨olt´es˝ u l´ad´aba helyezz¨ uk el. Az algoritmus versenyk´epess´eg´ere vonatkozik az al´abbi ´all´ıt´as. 18. T´ etel. [7] A TwoBins algoritmus a p ≥ 1 parametrikus probl´ema eset´en (4p+1)(p+1) epes. Ez a legjobb el´erhet˝ o versenyk´e2p(2p+1) versenyk´ pess´eg, nincs olyan online algoritmus, amelynek a versenyk´epess´ege kisebb, mint ez az ´ert´ek. Megvizsg´ altuk az u ¨temez´es ter¨ ulet´er˝ ol ´ atvett Lista algoritmus viselked´es´et is, amely a t´ argyat azon l´ ad´ aba rakja, ahol a legkisebb a t¨ olt´es. Ha t¨ obb ilyen l´ ada is van, akkor a legels˝o ilyen l´ad´at haszn´ alja. Az algoritmus azon speci´ alis f´elig-online esetekben igaz´an hat´ekony, amikor a t´ argyakat m´eret szerint monoton sorrendben kapjuk. Ezt mutatj´ ak az al´ abbi eredm´enyek. 19. T´ etel. [7] Ha a parametrikus esetben a t´ argyak m´eret szerint monoton nemcs¨ okken˝ o sorrendben ´erkeznek, akkor a Lista algoritalis esetben ez a legjobb mus versenyk´epess´ege 2p+1 2p . Ebben a speci´
17
Powered by TCPDF (www.tcpdf.org)
dc_1179_16
el´erhet˝ o versenyk´epess´eg, nincs olyan f´elig-online algoritmus, amelynek a versenyk´epess´ege kisebb, mint ez az ´ert´ek. 20. T´ etel. [7] Ha p = 1 ´es a t´ argyak m´eret szerint monoton nemn¨ ovekv˝ o sorrendben ´erkeznek, akkor a Lista algoritmus versenyk´ealis esetben is ez a legjobb el´erhet˝ o versenypess´ege 56 . Ebben a speci´ k´epess´eg. A p > 1 esetben nemn¨ ovekv˝ o sorozatokra a Lista algoritmus nem ´eri el a lehet˝ o legkisebb versenyk´epess´eget. Erre az esetre a TwoBinsDecreasing (TBD) algoritmust fejlesztett¨ uk ki. Az els˝o p darab t´ argyat az els˝ o l´ ad´ ahoz, a m´ asodik p darab t´argyat a m´asodik l´ ad´ ahoz rendelj¨ uk. A tov´ abbi t´ argyakat mindig ahhoz a l´ad´ahoz rendelj¨ uk, ahol kisebb a t¨ olt´es. Az algoritmus versenyk´epess´eg´et hat´ arozza meg az al´ abbi ´ all´ıt´ as. 21. T´ etel. [7] A TBD algoritmus 2p+3 epes monoton nem2p+2 -versenyk´ n¨ ovekv˝ o t´ argysorozatok eset´en minden p ≥ 2-re. Minden p ≥ 2 eset´en ez a legkisebb versenyk´epess´eg, ami monoton nemn¨ ovekv˝ o sorozatokra el´erhet˝ o. 3.4.2.
´ Altal´ anos l´ adasz´ am
Az ´ altal´ anos esetben csak a f´elig-online monoton sorozatok eset´et vizsg´ aljuk. Az, hogy van -e 2-n´el kisebb aszimptotikus versenyk´epess´eggel rendelkez˝ o algoritmus az ´ altal´ anos esetben tov´abbra is ny´ılt k´erd´es. Arra az esetre, ahol a t´ argyak monoton nemcs¨okken˝o sorrendben ´erkeznek a PackIncreasing (PI) algoritmust defini´altuk. Az algoritmus k´et ( 34 ≤ α ≤ 56 ´es 18 ≤ β ≤ 14 ) param´etert haszn´al, amelyeket a versenyk´epess´egi elemz´es sor´ an optimaliz´altunk. A t´argyakat m´eret szerint oszt´ alyokra bontjuk. A legfeljebb 12 m´eret˝ u t´argyakat kicsinek, azon t´ argyakat, amelyek m´erete a ( 21 , α] intervallumba esik k¨ ozepesnek, az α-n´ al nagyobb m´eret˝ u t´ argyakat pedig nagynak h´ıvjuk. Mivel monoton nemcs¨ okken˝ o sorrendben ´erkeznek a t´argyak, ez´ert tudjuk, hogy els˝ ok´ent a kicsi, majd a k¨ ozepes, v´eg¨ ul a nagy t´ argyak fognak meg´erkezni. A m´ asik β param´eter szerepe az, hogy az els˝ o bβmc l´ ad´ at foglaltnak nevezz¨ uk (tulajdonk´eppen ezek a l´ad´ak arra v´ arnak, hogy a k´es˝ obb esetlegesen megjelen˝o nagy t´argyakat j´ol
18
Powered by TCPDF (www.tcpdf.org)
dc_1179_16
tudjuk pakolni). A t¨ obbi l´ ad´ at szabadnak h´ıvjuk. A PI algoritmus a k¨ ovetkez˝ ok´eppen m˝ uk¨ odik. Am´ıg kis t´ argyak ´erkeznek ´es van legal´ abb egy foglalt l´ada, amiben a t¨ olt´es kisebb, mint 1 − α, addig pakoljuk a t´argyakat a Lista algoritmus alapj´ an a foglalt l´ ad´ akba. Ha ezt az´ert hagyjuk abba, mert elfogynak a kicsi t´ argyak ´es az els˝ o k¨ ozepes t´argy meg´erkezik, akkor a nf algoritmust haszn´ aljuk a szabad l´ad´akra, ami mindig az aktu´ alis l´ ad´ aba rakja a t´ argyakat, am´ıg azt le nem fedte ´es ezt k¨ ovet˝ oen t´er ´ at a k¨ ovetkez˝ o l´ ad´ ara. A szabad l´ad´ak lefed´ese ut´an az Lista algoritmust haszn´ aljuk a foglalt l´ ad´ akra, am´ıg azokat is lefedj¨ uk. Ha az algoritmus els˝ o r´esz´et nem egy k¨ozepes t´argy miatt, hanem az´ert hagyjuk abba, mert minden foglalt l´ada t¨olt´ese el´erte az 1 − α korl´ atot, akkor a pakol´ ast az nf elj´ ar´ assal folytatjuk els˝ok´ent a szabad l´ ad´ akat, majd a foglalt l´ ad´ akat pakolva. Az elj´ ar´ as versenyk´epess´eg´ere vonatkozik az al´abbi ´all´ıt´as. 22. T´ etel. [7] Az α ´es β param´eterek megfelel˝ o v´ alaszt´ asa mellett a PI algoritmus aszimptotikus versenyk´epess´ege legfeljebb 1.931215 monoton nemcs¨ okken˝ o m´eret˝ u sorozatok eset´en. Abban az esetben, ahol a t´ argyak sorozata m´eret szerint monoton nemn¨ ovekv˝ o sorrendben ´erkezik hat´ekonyabb algoritmust tudtunk fejleszteni. Ennek oka az, hogy a f˝ o neh´ezs´egeket val´oj´aban a nagyobb m´eret˝ u t´ argyak okozhatj´ ak, ´ıgy el˝ ony˝ os ha azokat az algoritmus m´ ar akkor l´ atja, amikor sok d¨ ont´esi lehet˝os´ege van. A kifejlesztett elj´ ar´ as ismertet´ es´ehez jel¨ olje h azon t´ argyak sz´am´at, ame 2 lyek m´erete a , 1 intervallumban, ` azon t´ a rgyak sz´am´at, amelyek 3 m´erete a 12 , 23 intervallumban van. Fontos megjegyezni, hogy ezeket a sz´ amokat nem ismerj¨ uk az elj´ ar´ as kezdetekor, ezeket online tudjuk meg, ahogy a t´ argyak ´erkeznek. A PD algoritmus ezen ´ert´ekekt˝ ol f¨ ugg˝ oen pakolja a be´erkez˝o t´ argyakat. Feltessz¨ uk, hogy nincs olyan t´ argy, amelynek a m´erete 1. Ez nem jelent megszor´ıt´ ast, hiszen az ilyen t´argyak ¨onmagukban lefednek egy l´ ad´ at ´es mivel els˝ ok´ent ´erkezn´enek, ez´ert ezt az online algoritmus is meg tudja tenni vel¨ uk. Ebb˝ ol ad´ od´oan ilyen t´argyak jelenl´ete csak jav´ıtan´ a a versenyk´epess´eget. Az els˝o min{h, m} t´argyak mindegyik´et k¨ ul¨ onb¨ oz˝ o l´ ad´ akba (az els˝ o min{h, m} l´ad´aba) pakoljuk. Ezt k¨ ovet˝ oen az al´ abbi 3 esetet k¨ ul¨ onb¨ oztetj¨ uk meg: 1. eset h ≥ m. Ekkor a k¨ ovetkez˝ o m t´argyat is egym´ast´ol k¨ ul¨ onb¨ oz˝ o l´ ad´ akba helyezz¨ uk, u ´gy hogy az els˝o 2m t´argy ut´an az 19
Powered by TCPDF (www.tcpdf.org)
dc_1179_16
i-edik l´ ada az i-edik ´es a 2m + 1 − i-edik t´ argyakat tartalmazza. Ha maradt m´eg olyan l´ ada, amit nem fedt¨ unk le, haszn´aljuk a nf algoritmust ezek lefed´es´ehez. 2. eset: h < m, 2(m − h) ≤ `. Ekkor pakoljuk a k¨ovetkez˝o 2(m − h) t´ argyat kettes´evel rendre a h + 1, . . . , m index˝ u l´ad´akba, majd a k¨ ovetkez˝ o h t´ argyat rakjuk az els˝ o h l´ ad´aba, az ott tal´alhat´o 2/3-n´ al nagyobb t´ argyak mell´e. V´eg¨ ul, ha maradt m´eg olyan l´ada, amit nem fedt¨ unk le, haszn´ aljuk a nf algoritmust ezek lefed´es´ehez. 3. eset: h < m, 2(m − h) > `. Ebben az esetben legyen h0 = ` 0 b 2 c. A k¨ ovetkez˝ o 2h t´ argyat pakoljuk p´ aronk´ent a h + 1, . . . , h + h0 index˝ u l´ ad´ akba, azaz a k¨ ovetkez˝ o m´eg u ¨res l´ad´akba, amik nem tartalmaznak 2/3-n´ al nagyobb t´ argyat. Megjegyezz¨ uk, hogy ezeket a l´ ad´ akat az algoritmus a p´ arokkal le is fedi. Ha ` p´aratlan, akkor az utols´ o ilyen t´ argyat a h + h0 + 1 ≤ m index˝ u l´ad´aba rakjuk. Ezt k¨ ovet˝ oen a tov´ abbi 2(m − h) − ` t´ argyat u ´gy pakoljuk el, hogy az els˝ o nagy t´ argyakat tartalmaz´ o h darab l´ ad´ aba ne ker¨ ulj¨on bel˝ol¨ uk ´es a t¨ obbi l´ ada mindegyik´eben pontosan k´et t´ argy legyen. Majd a k¨ ovetkez˝ o m − h0 t´ argyb´ ol rakjunk egyet-egyet a m´eg nem lefedett l´ ad´ ak mindegyik´ebe az els˝ o h l´ ad´ aval kezdve. V´eg¨ ul, ha maradt m´eg lefedetlen l´ ada, haszn´ aljuk a nf algoritmust ezek lefed´es´ere. Fontos megjegyezni, hogy a 2. ´es 3. eset ugyan´ ugy pakolja a t´ argyakat, am´ıg ` ´ert´ek´et meg nem tudjuk, ´ıgy val´oban online v´egrehajthat´ o az elj´ ar´ as. Az algoritmus versenyk´epess´eg´ere vonatkozik az al´ abbi ´ all´ıt´ as. 23. T´ etel. [7] A PD algoritmus aszimptotikusan 34 -versenyk´epes, ha a t´ argyak sorozata m´eret szerint monoton nemn¨ ovekv˝ o. Az m = 2 esettel ellent´etben nem siker¨ ult a lehet˝o legkisebb aszimptotikus versenyk´epess´eggel rendelkez˝ o algoritmusokat megtal´ alni. Az al´ abbi als´ o korl´ atot igazoltuk a lehets´eges versenyk´epess´egi h´ anyadosra. 24. T´ etel. [7] Nincs olyan f´elig-online algoritmus, amely aszimptotikus versenyk´epess´ege kisebb, mint 1.302017 monoton nemcs¨ okken˝ o sorozatok eset´en. Nincs olyan f´elig-online algoritmus, amely aszimptotikus versenyk´epess´ege kisebb, mint 10 o9 ≈ 1.111 monoton nemn¨ vekv˝ o sorozatok eset´en. Megeml´ıtj¨ uk, hogy a disszert´ aci´ oban a f´elig-online esetekben az 20
Powered by TCPDF (www.tcpdf.org)
dc_1179_16
als´ o korl´ atokat a parametrikus esetekre igazoltuk, de itt csak a p = 1 esetre vonatkoz´ o eredm´enyt emelt¨ uk ki.
4.
Online klaszterez´ es
Az online klaszterez´esi probl´em´ akban egy metrikus t´er pontjait szeretn´enk online csoportos´ıtani. Ez azt jelenti, hogy egyenk´ent ´erkeznek k´er´esek a t´er pontjaiba ´es minden k´er´est egy klaszterhez kell rendeln¨ unk az ´erkez´esekor a tov´ abbi k´er´esekre vonatkoz´o inform´aci´ok n´elk¨ ul. Egy pontot vagy egy meglev˝ o klaszterhez rendelhet¨ unk vagy u ´j klasztert defini´ alunk hozz´ a. A c´elunk a klaszterez´es teljes k¨olts´eg´enek minimaliz´ al´ asa, amely k¨ olts´eg az egyes klaszterek k¨olts´egeinek osszege. A klaszterek k¨ ¨ olts´ege f¨ ugghet a klaszterhez rendelt pontokt´ ol illetve a klaszter k¨ oz´eppontj´ at´ ol. Az egyik sz´eles k¨ orben vizsg´ alt online klaszterez´esi probl´ema az, amelyben egys´egnyi m´eret˝ u klasztereket kell l´etrehozni, azaz a c´elunk az, hogy minim´ alis sz´ am´ u egys´egg¨ ombbel fedj¨ uk le a pontokat. Ezt a probl´em´ at k´et k¨ ul¨ onb¨ oz˝ o online modellben vizsg´alt´ak att´ ol f¨ ugg˝ oen, hogy milyen m´ert´ekben kell r¨ ogz´ıtenie egy l´etrehozott g¨ ombnek a poz´ıci´ oj´ at az algoritmusnak. A szigor´ u modellben a g¨omb l´etrehoz´ asakor r¨ ogz´ıteni kell annak a hely´et is ´es a g¨omb nem mozgathat´ o k´es˝ obb. Ezt modellt a [6] cikkben defini´alt´ak, ahol egy O(2d d log d)-versenyk´epes algoritmust adtak meg d-dimenzi´os t´erre ´es egy Ω(log d/ log log log d) als´ o korl´ atot. Egy ´es k´et dimenzi´oban ´eles korl´ atokat bizony´ıtottak, az optim´ alis online algoritmusok 2 illetve 4-versenyk´epesek. A laza modellben a k¨or¨ok mozgathat´oak azon felt´etel mellett, hogy az eddig lefedett k´er´eseket tov´abbra is lefedik. Ezzel a k´erd´essel m´ ar egy dimenzi´ oban is t¨obb cikk foglalkozott, egyre jobb algoritmusokat defini´ altak ´es az als´o korl´at is n¨ ovekedett az els˝ o publik´ aci´ ot k¨ ovet˝ oen. A jelenlegi legjobb algoritmus, amit a [13] cikkben publik´ altak, 5/3-versenyk´epes. A legjobb als´ o korl´ atot, ami azt mondja ki, hogy nincs jobb algoritmus, mint 1.625-versenyk´epes a [28] cikkben publik´ alt´ ak. Egy m´ asik vizsg´ alt online klaszterez´esi feladat az online kiszolg´al´o elhelyez´esi probl´ema. A kiszolg´ al´ o elhelyez´esi probl´em´aban adott egy metrikus t´er k´er´esek egy multihalmaz´ aval (minden k´er´es a t´er egy pontja). A c´el kiszolg´ al´ oknak olyan elhelyez´ese a t´erben, amely elhelyez´esre minim´ alis a kiszolg´ al´ ok l´etrehoz´ asi k¨olts´eg´enek ´es a ki-
21
Powered by TCPDF (www.tcpdf.org)
dc_1179_16
szolg´ al´ as k¨ olts´eg´enek az ¨ osszege. Minden k´er´esre a kiszolg´al´as k¨olts´ege megegyezik a legk¨ ozelebbi kiszolg´ al´ ot´ ol vett t´avols´aggal. Az online v´ altozatban a k´er´esek egyenk´ent jelennek meg ´es minden k´er´es ´erkez´ese eset´en van lehet˝ os´ege az algoritmusnak u ´j kiszolg´al´ot, vagy kiszolg´ al´ okat nyitnia. A feladatot a [29] cikkben defini´alt´ak, ahol igazolt´ ak, hogy nincs konstans versenyk´epes algoritmus a feladat megold´ as´ ara ´es megadtak egy v´eletlen´ıtett O(log n)-versenyk´epes algoritmust. K´es˝ obb a [19] cikkben oldott´ ak meg teljesen a probl´em´at, ahol egy O(log n/ log log n)-versenyk´epes algoritmust adtak meg, ´es igazolt´ ak, hogy nincs olyan algoritmus, amely versenyk´epess´ege kisebb, mint Ω(log n/ log log n). Mi az egys´egg¨ omb¨ okkel val´ o klaszterez´es egy olyan kiterjeszt´es´et vizsg´ altuk, ahol a lefed˝ o klaszterek m´erete nem felt´etlen¨ ul egyenl˝o, hanem a klaszter m´erete is r´esze a c´elf¨ uggv´enynek. A probl´em´at egy dimenzi´ oban vizsg´ altuk az eredm´enyeink a [8] cikkben ker¨ ultek publik´ al´ asra. A modellben keletkezett klaszterez´es k¨olts´ege a l´etrehozott klaszterek k¨ olts´egeinek ¨ osszege, ´es egy klaszter k¨olts´ege egy egys´egnyi setup k¨ olts´eg plusz a klaszter ´ atm´er˝ oj´enek a hossza. Att´ol f¨ ugg˝oen, hogy milyen m´ert´ekben kell specifik´ alnia az algoritmusnak egy klasztert annak l´etrehoz´ asakor k´et k¨ ul¨ onb¨ oz˝ o v´ altozatot vizsg´altunk. A szigor´ u modellben a l´etrehozott klaszternek meg kell adni a m´eret´et ´es r¨ ogz´ıteni az elhelyezked´es´et. A laza modellben a klaszter m´erete n¨ ovelhet˝ o, ´es a klaszter is mozgathat´ o azon felt´etel mellett, hogy az addig lefedett pontokat tov´ abbra is lefedi. Megjegyezz¨ uk, hogy a [8] cikkben egy ´ atmeneti modellt is elemezt¨ unk, ahol a klaszter l´etrehoz´ asakor r¨ ogz´ıteni kell annak m´eret´et, de a klaszter mozgathat´ o azon felt´etel mellett, hogy az addig lefedett pontokat tov´abbra is lefedi, de ezeket az eredm´enyeket nem mutattuk be a disszert´a´ ci´ oban. Erdemes megjegyezni, hogy m´ıg a szigor´ u modellben egy klaszter k¨ olts´ege eld˝ ol annak l´etrehoz´ asakor, addig a laza modellben ez a k¨ olts´eg az algoritmus fut´ asa k¨ ozben n¨ ovekedhet. A laza modellben az ECC Extend closed clusters algoritmust vizsg´ altuk. Az algoritmus ismertet´es´ehez jel¨olje p az ´erkez˝o pont hely´et. Ha az algoritmusnak van olyan intervalluma (klasztere), ami tartalmazza p-t, akkor rendelj¨ uk p-t ehhez az intervallumhoz. Egy´ebk´ent pedig legyen q a p-hez legk¨ ozelebbi az eddig meg´ √ erkezett pontok k¨ oz¨ ul. Ha q ´es p t´ avols´ aga legfeljebb φ = (1 + 5)/2, akkor rendelj¨ uk p-t a q-t tartalmaz´ o klaszterhez, ´es ny´ ujtsuk meg az klasztert le´ır´ o intervallumot p-ig. Egy´ebk´ent pedig nyissunk egy u ´j 22
Powered by TCPDF (www.tcpdf.org)
dc_1179_16
klasztert, egy intervallumot, ami csak a p pontot tartalmazza. Siker¨ ult meghat´ aroznunk az algoritmus versenyk´epess´egi h´anyados´ at, ´es azt is igazoltuk, hogy az algoritmus a lehet˝o legjobb a versenyk´epess´eg szempontj´ ab´ ol. √ 25. T´ etel. [8] Az ECC algoritmus (1 + 5)/2-versenyk´epes. Nincs olyan algoritmus a laza modellben, amely versenyk´epess´ege kisebb, √ mint (1 + 5)/2. Vizsg´ altuk a probl´ema f´elig-online v´ altozat´ at is, ahol felt´etelezz¨ uk, hogy a pontok monoton n¨ ovekv˝ o sorrendben ´erkeznek. Ebben a speci´ alis esetben megadhat´ o az optim´ alis offline megold´as online m´ odon is, akkor kell u ´j klaszter nyitni, ha az u ´j pontnak ´es az utolj´ara nyitott klaszter sz´el´enek a t´ avols´ aga nagyobb, mint 1. A szigor´ u modellben az al´ abbi Center algoritmust vizsg´altuk. Az algoritmus megad´ as´ ahoz jel¨ olje az u ´j pont hely´et p. Ha az algoritmusnak van olyan intervalluma (klasztere), ami tartalmazza p-t, akkor rendelj¨ uk p-t ehhez az intervallumhoz. Ellenkez˝o esetben legyen ` a legk¨ ozelebbi balra es˝ o fedett pont (ha nincs ilyen ` = −∞), ´es legyen r a legk¨ o zelebbi jobbra es˝ o fedett pont (ha nincs ilyen r = ∞) √ 2 ´es legyen α = 2 . Nyissuk meg p-hez a [max{`, p−α}, min{p+α, r}] √ klasztert. Teh´ at az alap¨ otlet az, hogy egy p k¨ ozep˝ u 2 m´eret˝ u klasztert nyitunk. M´ asr´eszt, ha ez a klaszter belemetszene a szomsz´edos, m´ ar meglev˝ o klaszterekbe akkor a m´eret´et cs¨okkentj¨ uk. Siker¨ ult meghat´ aroznunk az algoritmus versenyk´epess´egi h´anyados´at, ´es azt is igazoltuk, hogy az algoritmus a lehet˝ o legjobb algoritmus versenyk´epess´eg szempontj´ ab´ ol. √ 26. T´ etel. [8] Az Center algoritmus (1+ 2)-versenyk´epes. Nincs olyan algoritmus u modellben, amely versenyk´epess´ege ki√ a szigor´ sebb, mint 1 + 2. Ebben a modellben is vizsg´ altuk azt a f´elig online esetet, ha a pontok monoton n¨ ovekv˝ o sorrendben ´erkeznek. Itt egy 2-versenyk´epes algoritmust adtunk meg ´es igazoltuk, hogy nincs olyan algoritmus, amelynek kisebb a versenyk´epess´ege. K´es˝ obb az ´ altalunk bevezetett modell t¨ obbdimenzi´os kiterjeszt´eseivel kapcsolatos eredm´enyek is publik´ al´ asra ker¨ ultek. Azt a modellt, ahol a klaszter k¨ olts´ege egy konstans setup k¨olts´egnek ´es a klaszter ´ atm´er˝ oj´enek az ¨ osszege, a [20] cikk vizsg´alta, ahol igazol´ast 23
Powered by TCPDF (www.tcpdf.org)
dc_1179_16
nyert, hogy magasabb dimenzi´ okban nincs konstans versenyk´epes algoritmus. A k´et-dimenzi´ os modellt, ahol a k¨olts´eg az ´atm´er˝o n´egyzet´et˝ ol f¨ ugg a [11] cikkben vizsg´ altuk. Igazoltuk, hogy ezen f¨ uggv´eny mellett van konstans versenyk´epes elj´ar´as.
Hivatkoz´ asok [1] N. Alon, Y. Azar, J. Csirik, L. Epstein, S.V. Sevastianov, A.P.A. Vestjens, G.J. Woeginger, On-line and off-line approximation algorithms for vector covering problems, Algorithmica, 21, 104–118, 1998. [2] S.F. Assmann, D.S. Johnson, D.J. Kleitman, J.Y.T. Leung, On a dual version of the one-dimensional bin packing problem, Journal of Algorithms, 5(4), 502–525, 1984. [3] Y. Azar, J. Boyar, L. Epstein, L.M. Favrholdt, K.S. Larsen, M.N. Nielsen, Fair versus unrestricted bin packing, Algorithmica, 34, 181–196, 2002. [4] L. Babel, B. Chen, H. Kellerer, V. Kotov, Algorithms for online bin-packing problems with cardinality constraints, Discrete Applied Mathematics, 143(1-3) 238–251, 2004. [5] J. Balogh, J. B´ek´esi, G. Galambos, New lower bounds for certain classes of bin packing algorithms, Theoretical Computer Science, 440–441, 1–13, 2012 [6] M. Charikar, C. Chekuri, T. Feder, R. Motwani, Incremental clustering and dynamic information retrieval, SIAM Journal on Computing, 33(6), 1417–1440, 2004. [7] J. Csirik, L. Epstein, Cs. Imreh, A. Levin, On the sum minimization version of the online bin covering problem, Discrete Applied Mathematics, 158(13) 1381–1393, 2010. [8] J. Csirik, L. Epstein, Cs. Imreh, A. Levin, Online Clustering with Variable Sized Clusters, Algorithmica, 65(2), 251–274, 2013. [9] J. Csirik, V. Totik. On-line algorithms for a dual version of bin packing. Discrete Applied Mathematics, 21, 163–167, 1988. 24
Powered by TCPDF (www.tcpdf.org)
dc_1179_16
[10] J. Csirik, G. Woeginger, Shelf algorithms for on-line strip packing, Information Processing Letters, 63, 171–175, 1997. [11] G. Div´eki, Cs. Imreh, An online 2-dimensional clustering problem with variable sized clusters, Optimization and Engineering, 14(4), 575–593, 2013. [12] Gy. D´ osa, Cs. Imreh, The generalization of scheduling with machine cost, Theoretical Computer Science, 510, 102–110, 2013. [13] M.R. Ehmsen, K.S. Larsen, Better bounds on online unit clustering, In Proc. of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT2010), 371–382, 2010. [14] L. Epstein, Online bin packing with cardinality constraints, SIAM Journal on Discrete Mathematics, 20(4), 1015–1030, 2006. [15] L. Epstein, L.M. Favrholdt, On-Line maximizing the number of items packed in variable-sized bins, Acta Cybernetica, 16, 57–66, 2003. [16] L. Epstein, Cs. Imreh, A. Levin, Class constrained bin packing revisited, Theoretical Computer Science, 411(34–36), 3073– 3089, 2010 [17] L. Epstein, Cs. Imreh, A. Levin, Class Constrained Bin Covering, Theory of Computing Systems, 46(2), 246–260, 2010. [18] L. Epstein, Cs. Imreh, A. Levin, Bin covering with cardinality constraints, Discrete Applied Mathematics, 161(13–14), 1975– 1987, 2013. [19] D. Fotakis, On the competitive ratio for online facility location, Algorithmica, 50(1), 1–57, 2008. [20] D. Fotakis, P. Koutris, Online Sum-Radii Clustering, Theoretical Computer Science, 540 27–39, 2014 [21] R.L. Graham, Bounds for certain multiprocessor anomalies, Bell System Technical J., 45, 1563–1581, 1966.
25
Powered by TCPDF (www.tcpdf.org)
dc_1179_16
[22] R. Harren, W. Kern, Improved lower bound for online strip packing, in Proceedings of the 9th International Workshop on Algorithms and Online Algorithms, LNCS 7164, 211–218, 2011. [23] J.L. Hurink, J.J. Paulus, Improved online algorithms for parallel job scheduling and strip packing, Theoretical Computer Science, 412(7), 583–593, 2011. [24] Cs. Imreh, Online strip packing with modifiable boxes, Operations Research Letters, 29, 79–86, 2001. [25] Cs. Imreh, Scheduling problems on two sets of identical machines, Computing, 70, 277–294, 2003. [26] Cs. Imreh, On-line scheduling with general machine cost functions, Discrete Applied Mathematics, 157, 2070–2077, 2009. [27] Cs. Imreh, J. Noga, Scheduling with Machine Cost, In Randomization Approximation and Combinatorial Optimization Algorithms and Techniques ed. D. Hochbaum and K. Jansen, 1999, 168–176. [28] J. Kawahara, K.M. Kobayashi, An improved lower bound for one-dimensional online unit clustering, Theoretical Computer Science, 600, 171–173, 2015 [29] A. Meyerson, Online facility location, In Proc. of the 42nd Annual Symposium on Foundations of Computer Science (FOCS2001), 426–431, 2001. [30] S.S. Seiden, On the online bin packing problem, Journal of the ACM, 49(5) 640–671, 2002. [31] H. Shachnai, T. Tamir, Tight bounds for online classconstrained packing, Theoretical Computer Science, 321(1), 103–123, 2004. [32] E.C. Xavier, F.K. Miyazawa. The class constrained bin packing problem with applications to video-on-demand, In Proc. of the 12th Annual International Conference on Computing and Combinatorics (COCOON 2006), 439–448, 2006. [33] D. Ye, X. Han, G. Zhang, A note on online strip packing, Journal of Combinatorial Optimization, 17(4), 417–423, 2009.
26
Powered by TCPDF (www.tcpdf.org)
