Eötvös Loránd Tudományegyetem Természettudományi Kar
Vass Balázs
Online algoritmusok árverési feladatokban BSc Szakdolgozat
Témavezet®k:
Kovács Erika Renáta
Long Tran-Thanh
ELTE, Operációkutatási Tanszék
University of Southampton
Budapest, 2014
Köszönetnyilvánítás Ezúton szeretném megköszönni Kovács Erika Renátának, hogy a témaválasztástól kezdve az apró részletekkel kapcsolatos észrevételekig kitartóan vezetett szakdolgozatom megalkotása alatt. Köszönet Long Tran-Thanhnak az általa mutatott madártávlatért és az ismeretlent feszeget® kérdéseiért és válaszaiért. Köszönet mindazoknak, akik a matematika útját mutatták nekem. Köszönöm az egyetemnek és környezetemnek a légkört, amivel körbevett. Köszönöm a napnak, hogy sütött, az es®nek, hogy esett, a húroknak, hogy zengettek, a színeknek, hogy meglettek. Örömmel végeztem a munkát.
2
Tartalomjegyzék El®szó
4
1. Szubmoduláris függvények
6
1.1.
Szubmoduláris függvények és tulajdonságaik
. . . . . . . . . . . . . . . . .
1.2.
Szubmoduláris függvények o ine maximalizálása
. . . . . . . . . . . . . . .
2. Online algoritmusok
6 11
13
2.1.
Determinisztikus online algoritmusok . . . . . . . . . . . . . . . . . . . . . .
13
2.2.
Példa: lapozási feladat
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
2.3.
Véletlen online algoritmusok . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
2.4.
Példa: maximális párosítás online keresése . . . . . . . . . . . . . . . . . . .
22
3. Online szubmoduláris árverések
26
3.1.
Online szubmoduláris árverések . . . . . . . . . . . . . . . . . . . . . . . . .
26
3.2.
Ellenféllel szemben
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
3.2.1.
Azonos tárgyak esetén . . . . . . . . . . . . . . . . . . . . . . . . . .
29
3.2.2.
Azonos haszonfüggvények esetén
. . . . . . . . . . . . . . . . . . . .
29
Független azonos eloszlású sztochasztikus bemenettel . . . . . . . . . . . . .
32
3.3.1.
37
3.3.
3.4.
Azonos tárgyak esetén . . . . . . . . . . . . . . . . . . . . . . . . . .
Összefoglalás
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Irodalomjegyzék
38
39
3
El®szó Bizonyára többen találkoztak már Szindbád esetével a háremhölgyekkel, mely gyakran felbukkanó feladat a magyar szakirodalomban. Leírása a következ®. Szindbád megmentette a kalifa életét, és ezért jutalmul feleségül veheti egyik háremhölgyét. A háremhölgyek sorban vonulnak el Szindbád el®tt, egyszerre csak egyik®jük van jelen. Szindbád minden háremhölgy szépségét össze tudja hasonlítani a már elhaladottakéval, és egyértelm¶en meg tudja állapítani, hogy az eddig látott háremhölgyek közül ki a legszebb. Egy éppen megjelent háremhölgyr®l megjelenése után azonnal el kell döntse, hogy ®t akarja-e feleségül venni, és ezt a döntést késõbb nem változtathatja meg. Szindbád tudja, hogy a kalifának hány háremhölgye van, viszont nem tudja, hogy a még nem látott háremhölgyek milyen szépek. A háremhölgyek véletlen sorrendben jelennek meg, és minden sorrend egyformán valószín¶. Szindbád szeretné a legcsinosabb háremhölgyet választani. Milyen algoritmussal tudja ezt a lehetõ legnagyobb valószín¶séggel elérni, és mekkora ez a valószín¶ség? A feladat megoldása szerint Szindbád számára az a legígéretesebb, ha elengedi a háremhölgyek b® egyharmadát, megjegyzi, milyen szép volt közülük a legszebb, majd a következ®kben az els® annál is csinosabbat kéri magának. Ekkor b® egyharmad eséllyel szerzi meg a legszebbet. A Szindbád-probléma ismertségén kívül két szempontból is jó példa. Egyrészt
online
feladat abban az értelemben, hogy Szindbád még az adatok (azaz a háremhölgyek egymáshoz viszonyított szépsége) érkezése alatt, ám az összes adat ismerete nélkül kénytelen visszavonhatatlan döntéseket hozni, melyekr®l kiderülhet, hogy nem voltak tökéletesek. Mint érezzük, nem várhatjuk, hogy az online feladatokat jobban meg tudjuk oldani, mint az
o ine
párjaikat (amikor az összes adat birtokában hozhatjuk döntéseinket). Pél-
dánk o ine változatának megoldása nyilvánvaló: Szindbád összehasonlítja az ®t körülül® háremhölgyek külcsíneit, majd kiválasztja magának a legszebbet. Másrészt - egy kis fantáziával - Szindbád példája rávezet az árverési feladatokra. Képzeljük el, hogy Szindbád el szeretne venni egy olyan csinos háremhölgyet, akinek ® maga is rokonszenves. Tegyük fel továbbá, hogy Szindbád társaságában található Ali Baba és a
4
negyven rabló, akiknek Szindbáddal megegyez® szándékuk van. Miközben a háremhölgyek egyesével vonulnak el el®ttük (így a kölcsönös szimpátiák id®közben derülnek ki), céljuk minél több házasság köttetése. Természetesen amelyik hölgy elhaladt, már nem kérhet® vissza. E szakdolgozatban vizsgált árverési feladatok szintén online-ok. A következ®képp lehet elképzelni ®ket. Egy árverésen jelen van néhány ügynök, akik a szerre érkez® tárgyakra várnak. Minden ügynök esetén az általa éppen birtokolt tárgyak halmazának függvényében ismerjük, hogy mekkora hasznot hoz neki az éppen árverezend® tárgy, amennyiben hozzá kerül. Feladatunk az éppen érkez® tárgy hozzárendelése egy ügynökhöz úgy, hogy az ügynökök összhasznát (a közjót) az árverés során maximalizáljuk. A kezelhet®ség érdekében feltesszük, hogy egy új tárgy egy ügynöknek egy általa birtokolt b®vebb tárgyahalmaz esetén legfennebb akkora hasznot hoz, mint egy sz¶kebb halmaz esetén. Az ügynökök haszonfüggvényeinek ezt a tulajdonságát fogjuk
szubmodularitásnak
nevezni.
Nyilvánvalóan léteznek nem szubmoduláris árverések is (például jegygy¶r¶k párban szoktak hasznot hozni), ezekr®l nem lesz szó a szakdolgozatban. Megjegyzend® továbbá, hogy nem foglalkozunk az árverések játékelméleti vonatkozásaival. A szakdolgozat felépítése a következ®. Az els® fejezet rövid áttekintést ad a szubmoduláris függvények néhány tulajdonságáról, alkalmazási lehet®ségér®l és o ine maximalizálásáról. A második fejezetben el®ször bevezetjük a determinisztikus online algoritmusokat és a
c-közelít®ségük
fogalmát, majd a lapozási feladat példájában alkalmazzuk ezeket. A
második fejezet második felében bemutatjuk a véletlen online algoritmusokat, különböz® ellenfeleiket, az algoritmusok különböz® esetekben való
c-közelít®ségi
fogalmait, majd a
maximális párosítás online keresésén keresztül közelebbi képet alkotunk róluk. A harmadik fejezetben rátérünk az online szubmoduláris árverések és különböz® sajátos eseteik vizsgálatára. Ismeretes, hogy amennyiben az ügynökök haszonfüggvényei monoton szubmodulárisok, a mohó algoritmus által szolgáltatott megoldás biztosan eléri az optimum felét, azaz
1/2-közelít®.
Tavalyi, 2013-as eredmény, hogy ebben az esetben nem létezik a mohónál
lényegesen jobb, azaz
(1/2 + )-közelít®
algoritmus (ahol
> 0).
Long Tran-Thanh felve-
tése az volt, hogy vizsgáljuk meg a feladat speciális eseteit. Egy lehetséges eset az, amikor minden érkez® tárgy egyforma az ügynökök haszonfüggvényei számára. Könny¶ belátni, hogy ekkor a mohó algoritmus a feladat egy optimális megoldását szolgáltatja. Egy másik sajátos eset az, amikor az ügynökök haszonfüggvényei megegyeznek. Beláttuk, hogy a mohó algoritmus legfennebb
3/4-közelít® lehet. Nyitott kérdés azonban, hogy a közelít®ségi
hányadosa ténylegesen eléri-e ezt a számot, illetve, hogy létezik-e a mohónál hatékonyabb algoritmus.
5
1. fejezet
Szubmoduláris függvények 1.1. Szubmoduláris függvények és tulajdonságaik A szubmodularitás halmazfüggvények tulajdonsága. Legyen a
V
alaphalmaz véges, legyen
f : 2V → R halmazfüggvény, és f (∅) = 0. Az egyik legkézenfekv®bb példa a szubmoduláris függvények szemléltetésére a következ®. Tekintsük egy város vízvezeték-hálózatát, melybe id®nként szennyez®dés kerül. Szeretnénk érzékel®ket telepíteni ezek miel®bbi észlelése érdekében. Legyen
V
azon helyek halmaza, ahova szerelhet®k ezek,
f (S) pedig jelentse az S -beli
pontokra helyezett érzékel®k együttes hatékonyságát. A továbbiakban a szubmodularitás de niálása után megmutatjuk, hogyan is kerül el® a példánkban ez a tulajdonság.
1.1.1. De níció. (Diszkrét derivált) Egy
f : 2V → R halmazfüggvény, S ⊆ V , és
e ∈ V esetén legyen a ∆f (e|S) := f (S ∪ {e}) − f (S) kifejezés az f -nek S -ben vett e irányú
diszkrét deriváltja. Hasonlóan értelmezhet® a halmaz irányú diszkrét derivált. Legyen f és S mint az el®bb. Ekkor egy T ⊆ V esetén legyen a ∆f (T |S) := f (S ∪ T ) − f (S) kifejezés az f -nek S -ben vett T irányú diszkrét deriváltja. Amennyiben az
f
függvény egyértelm¶, gyakran elhagyjuk az alsó indexb®l, és egyszer¶en
a következ®t írjuk:
∆(e|S).
1.1.2. Megjegyzés.
T ⊆V
esetén legyen
∆(T |S) =
|T | X
tk T k -adik
eleme. Ekkor minden
S ⊆ V -re
∆(tk |S ∪ {tl |l ∈ 1, ..., k − 1}).
k=1
1.1.3. De níció. (Szubmodularitás) Egy f
: 2V → R függvény szubmoduláris, ha
minden A ⊆ B ⊆ V, e ∈ V \ B − re ∆(e|A) ≥ ∆(e|B). 6
(1.1)
1.1.4. Állítás. Egy f
: 2V → R függvény pontosan akkor szubmoduláris, ha
minden A, B ⊆ V − re f (A ∩ B) + f (A ∪ B) ≤ f (A) + f (B).
Bizonyítás.
El®ször azt mutatjuk meg, hogy (1.2)
esetén legyen
X=B
és
Y = A ∪ {e}.
⇒ (1.1). Adott A ⊆ B ⊆ V
(1.2)
és
e ∈ V \B
Ekkor (1.2) miatt igaz, hogy
f (X ∩ Y ) + f (X ∪ Y ) ≤ f (X) + f (Y ) f (A) + f (B ∪ {e}) ≤ f (B) + f (A ∪ {e}) f (B ∪ {e}) − f (B) ≤ f (A ∪ {e}) − f (A) ∆(e|B) ≤ ∆(e|A). ⇒
Most mutassuk meg, hogy (1.1) és
Y = A.
Mivel
X ⊆ Y,
(1.2). Adott
1.1.3 és (1.1) alapján
A
B\A
és
B⊆V
esetén legyen
elemeit egyenként,
X =A∩B
X -hez
és
Y -hoz
egyszerre véve azt kapjuk, hogy
∆(B \ A|X) ≥ ∆(B \ A|Y ) f ((B \ A) ∪ (A ∩ B)) − f (A ∩ B) ≥ f ((B \ A) ∪ A) − f (A) f (B) + f (A) ≥ f (A ∪ B) + f (A ∩ B). Gondoljuk most a diszkrét deriváltat haszonnak. A szubmodularitás de níciója által sugallt szemlélet szerint egy adott
e
elem hozzávétele egy egyre b®vül® halmazsorozathoz
nemnövekv® haszonnal jár, azaz a szubmoduláris függvények kielégítenek egy természetes tulajdonságot, amit a csökken® hasznok elvének nevezhetünk. Ennek észben tartása gyakran hasznunkra lehet a kés®bbiekben. A vízhálózatos példánkhoz készített ábra szemléletesen is mutatja a csökken® hasznokat. Legyen itt
Si
az a terület, ahol történt szennyezéseket az
érzékel® gyorsan érzékeli. Ha
s1
pített érzékel® hatókörnyezetébe
és
s2
Se
mellett telepítjük
s3 -at
és
si ∈ V s4 -et,
helyre telepített a több el®re tele-
nagyobb helyen metsz bele, azaz csökken a haszna:
∆(se |{s1 , s2 }) ≥ ∆(se |{s1 , s2 , s3 , s4 }).
7
S4
Sc
S1
S2
S3
Sc
S1
(a)
S2
(b)
1.1. ábra. Ugyanazon érzékel® hozzávétele egy sz¶kebb szenzorhalmazhoz legalább akkora hasznot hoz, mint egy b®vebb halmazhoz való hozzáadása
(a) (b).
Néhány gyakran el®forduló példa szubmoduláris függvényekre:
1.1.5. De níció.
f : 2V → R moduláris, ha minden A, B ⊆ V esetén f (A ∩ B) + f (A ∪
B) = f (A) + f (B).
1.1.6. Példa.
A moduláris függvények szubmodulárisak 1.1.4 alapján. Hasonlítanak a li-
neáris függvényekre, mivel a diszkrét deriváltjaik konstansok:
∆(e|B) = ∆(e|A)
minden
e 6∈ A ∪ B esetén. Ezért egy f moduláris függvény, feltéve, hogy f (∅) = 0, felírható X f (S) = w(e) alakban, ahol w : V → R megfelel® súlyfüggvény. A, B
és
e∈S
1.1.7. Példa.
Halmazok be- és kifok-függvénye szubmoduláris. Könnyen ellen®rizhet® az
1.1.4-es állítás segítségével.
1.1.8. De níció. (Monotonitás) Egy
f : 2V → R függvény monoton, ha minden A ⊆
B ⊆ V esetén f (A) ≤ f (B).
1.1.9. Megjegyzés.
Egy
nemnegatívak, azaz ha
f
függvény pontosan akkor monoton, ha a diszkrét deriváltjai
A ⊆ V
és
e ∈ V
esetén
∆(e|A) ≥ 0.
A monoton szubmoduláris
függvények egy fontos részhalmaza az, amelyre fennáll, hogy minden re
∆(e|A) ≥ ∆(e|B).
e∈V-
e∈ / B.
A súlyozott fedések szubmodulárisak. Legyen
w:X→R
a
g -hez
X
egy halmaz,
V pedig X [ X családja. Ekkor egy S ⊆ V részcsalád esetén az f (S) := g v =
moduláris függvény,
és
Ez a tulajdonság kissé különbözik a 1.1.3 de níciótól abban, hogy
nem szükséges az, hogy
1.1.10. Példa.
A⊆B⊆V
tartozó súlyfüggvény,
v∈S
x∈
S
g : 2X → R+
egy részhalmaz-
w(x) függvény
v∈S v
monoton szubmoduláris. Mindkét állítás könnyen ellen®rizhet®. A vízvezetékes példában adott
x
X
vonatkozhat szennyezési eseményekre,
esemény súlyosságát, és minden lehetséges
az észlelt
X -beli
eseményeket.
8
v ∈V
w(x)
mérheti egy
szenzorhelyhez hozzárendeljük
1.1.11. Példa.
V = {1, . . . , n}
Üzletláncok esetén tegyük fel, hogy egy
halmazból szeret-
nénk kiválasztani azokat a helyeket, ahol létesítményeket állítanánk fel adott kiszolgálására. A
j
helyen megnyitott létesítmény az
szolgáltatást , ahol
M ∈
i
vev® számára
Mi,j
m darab vev®
értékben nyújt
Rm×n . Amennyiben az összes vev® a számára legnagyobb érték¶
szolgáltatást nyújtó létesítményt választja, a vev®knek nyújtott szolgáltatások összértékét
j
f (S) =
m X
max Mi,j függvény szolgáltatja. Legyen itt f (∅) = 0. Ekkor ha minden j∈S i=1 esetén Mi,j ≥ 0, akkor könnyen belátható, hogy f (S) monoton szubmoduláris.
az
i
és
Ez a modell más alkalmazásokban is használható. Például az érzékel®-elhelyezési feladatunkban
Mi,j
vonatkozhat a
j
szenzor által az
i
esetben hozott haszonra, ahol a hasz-
nosságot például a szennyezés észlelési idejének várható csökkentésében mérhetjük. Most nézzük a szubmoduláris függvények néhány hasznos tulajdonságát.
1.1.12. Állítás. Szubmoduláris függvények nemnegatív lineáris kombinációja szubmoduláris. Más szóval ha g1 , ..., gn : 2V → R szubmoduláris és α1 , ..., αn ≥ 0, akkor f (S) :=
n X
αk gk (S) szubmoduláris.
k=1
Bizonyítás.
A de níció miatt szubmoduláris függvények nemnegatív számszorosa és összege
is szubmoduláris.
Az el®bbi tulajdonság szerint bonyolult szubmoduláris célfüggvényeket felírhatunk egyszer¶bb szubmoduláris alkotóelemek összegeként.
1.1.13. Állítás. Minden f szubmoduláris függvény és A, B ∈ V halmazok esetén f (A) + ∆(B|A) ≤ f (A) +
X
∆(e|A).
e∈B
Bizonyítás.
1.1.2 és 1.1.3 felhasználásával adódik.
Nézzük, mi a kapcsolat a szubmodularitás és a konkavitás között:
1.1.14. Állítás.
g : {0, ..., |V |} → R esetén f (S) := g(|S|) szubmoduláris ⇔ g konkáv.
Bizonyítás.
g
miatt
Ha
konkáv, az azt jelenti, hogy minden
∆f (e|S) ≥ ∆f (e|T ),
S ⊆ T ⊆ V, e ∈ V -re |S| ≤ |T |
ami épp a szubmodularitás de níciója. Visszafelé, legyen
szubmoduláris. Ekkor legyen
S0 ⊂ S1 ⊂ ... ⊂ S|V | = V . Ekkor minden 0 < k < |V |, e ∈ / Sk -
ra
∆f (e|Sk ) ≤ ∆f (e|Sk−1 ) g(k + 1) − g(k) ≤ g(k) − g(k − 1) g(k + 1) + g(k − 1) ≤ 2g(k), azaz
g
konkáv.
f
9
1.1.15. Állítás. A monoton szubmodularitás meg®rz®dik csonkoláskor: ha
f : 2V → R
monoton szubmoduláris, akkor g(S) := min{f (S), c} is az, bármely c ∈ R számra .
Bizonyítás.
Könnyen adódik a diszkrét deriváltas de nícióból.
Most nézzünk példát arra, hogy míg a csonkolás meg®rzi a szubmodularitást, két szubmoduláris függvény minimuma, maximuma és különbsége nem feltétlen szubmoduláris.
1.1.16. Példa. (Kivonás)
Legyen
V = {1, 2}.
Az els® oszlopban a függvények neve, az
els® sorban a behelyettesítési értékek olvashatók. Itt míg
f −g
nem szubmoduláris, mert
nem az, mert
∅
{1}
{2}
{1,2}
f
0
1
1
2
g
0
1
2
2
f −g
0
0
−1
0
g
monoton szubmoduláris,
Ugyanazokkal a jelölésekkel
f
és
g
szubmoduláris, de
h(∅) + h(1, 2) > h(1) + h(2). ∅
{1}
{2}
{1,2}
f
0
1
−1
0
g
0
−1
1
0
min(f, g)
0
−1
−1
0
1.1.18. Példa. (Maximumvétel) szubmoduláris, de
és
∆f −g (2|∅) < ∆f −g (2|{1}).
1.1.17. Példa. (Minimumvétel) h := min(f, g)
f
h := max(f, g)
Legyen V={1,2,3}, a jelösések az el®bbiek. Itt
nem az, mert
f
és
g
h(1) + h(1, 2, 3) > h(1, 2) + h(2, 3).
∅
{1}
{2}
{3}
{1,2}
{1,3}
{2,3}
{1,2,3}
f
0
0
0
1
0
1
1
1
g
0
1
0
1
0
1
0
0
max(f, g)
0
1
0
1
0
1
1
1
Míg a szubmoduláris függvények egyes tulajdonságai a konkáv függvényekére emlékeztetnek, úgy egyes tulajdonságuk a konvex függvényekkel hozza ®ket kapcsolatba. Ilyen például az, hogy a konvex függvényekhez hasonlóan, melyeket hatékonyan lehet minimalizálni, a szubmodulárisok minimalizálása lehetséges (er®sen) polinomiális id®ben [1].
10
1.2. Szubmoduláris függvények o ine maximalizálása U ⊆ 2V
Legyen dani a
halmazok családja,
U
elemeit hívjuk megengedetteknek. Szeretnénk megol-
max f (S) feladatot. Az erre a célra írt algoritmusok vizsgálatakor felmerül a kérdés, S∈U
hogy egy
S ⊆V
esetén hogy kapjuk meg
Feltesszük, hogy adott egy orákulum,
f (S) értéket. A legegyszer¶bb példa a megoldandó feladatra a számosságkorlátos, ahol U = {S |S| ≤ k} valamely k -ra. Már ez is NP-nehéz a mely minden
S -re
f (S)-et.
azonnal megadja az
szubmoduláris függvények több osztályára nézve [1]. Ebb®l adódóan érdemes tárgyalni az optimumot elméletileg is biztosan hatékonyan közelít® algoritmusokat.
1.2.1. Példa. (Mohó algoritmus)
A
max f (S) közelítésére monoton szubmoduláris függS∈U
vényeknél számosságkorlátos esetben kézenfekv® lehet®ség a mohó algoritmus, mely egy üres
S0
halmazból indul, és az
∆(e|Si−1 ),
i.
lépésben hozzávesz egy
e
elemet, melyre maximális a
azaz
Si = Si−1 ∪ {arg max ∆(e|Si−1 )}. e
A következ® tétel bizonyítja, hogy a mohó algoritmus közelítést ad az optimális megoldásra.
1.2.2. Tétel. (Nemhauser, Wolsey, Fisher 1978) [1] Legyen f
: 2V → R+ nemnega-
tív monoton szubmoduláris függvény, és legyenek {Si }i≥0 a mohó algoritmus által választott halmazok. Ekkor minden k, l ∈ N+ -ra f (Sl ) ≥ (1 − e−l/k ) max f (S). S:|S|≤k
Speciálisan, l = k-ra f (Sk ) ≥ (1 − 1/e) max f (S). S:|S|≤k
Bizonyítás.
Rögzítsük le
l-et
és
k -t.
Legyen
S ∗ ∈ arg max{f (S) : |S| ≤ k}.
nitás miatt az általánosság megszorítása nélkül feltehetjük, hogy
|S ∗ | = k .
∗ ∗ tetsz®leges sorbarendezése a következ®: {v1 , . . . , vk }. Ekkor minden
A monoto-
Legyen
i < l-re
S∗
egy
áll az alábbi
egyenl®tlenséglánc:
f (S ∗ ) ≤ f (S ∗ ∪ Si )
(1.3)
= f (Si ) + ∆(S ∗ |Si )
(1.4)
≤ f (Si ) +
X v∈S ∗
11
∆(v|Si )
(1.5)
k X (f (Si+1 ) − f (Si ))
≤ f (Si ) +
(1.6)
i=1
≤ f (Si ) + k(f (Si+1 ) − f (Si )) (1.3)
f
(1.7)
monotonitásából ered, (1.4) 1.1.2 miatt igaz, (1.5) 1.1.13-b®l következik, (1.6)
azért áll, mert
Si+1
mohón származott
Si -b®l,
(1.7) pedig azt használja ki, hogy
|S ∗ | ≤ k .
Tehát
f (S ∗ ) − f (Si ) ≤ k(f (Si+1 ) − f (Si )) Legyen
δi := f (S ∗ ) − f (Si ),
így (1.8)-et újraírhatjuk
δi ≤ k(δi − δi+1 )
(1.8) alakban, ezt átren-
dezve kapjuk:
δi+1
Ezért
(1.9)
l
δ0 . Jegyezzük meg, hogy δ0 = f (S ∗ ) − f (∅) ≤ f (S ∗ ), mert f ≥ 0. k −x , minden x ∈ R-re egyenl®tlenséggel adódik, hogy ismert 1 − x ≤ e
δl ≤
Ezekb®l a jól
1
1 δi . ≤ 1− k
1−
1 l δl ≤ 1 − δ0 ≤ e−l/k f (S ∗ ). k
(1.10)
δl helyére f (S ∗ )−f (Sl )-et helyettesítve, majd az egyenletet átrendezve kapjuk a keresett f (Sl ) ≥ (1 − e−l/k )f (S ∗ )
korlátot.
Bár a tételt eredetileg csak az
l = k esetre bizonyították, az l 6= k eset ismerete hasznos.
Például ha a szennyezési feladatban a mohó algoritmusnak megengedjük, hogy
5k
érzékel®t válasszon ki, akkor a
≈ 0.99-re
k
elem optimumának közelítési hányadosa
k
helyett
≈ 0.63-ról
n®.
Nemhauser és Wolsey ugyancsak 1978-ban bebizonyította, hogy nem létezik olyan polinomiális sok részhalmazt megvizsgáló algoritmus, mely az tudna.
12
(1 − 1/e)-közelítésnél
jobbat
2. fejezet
Online algoritmusok 2.1. Determinisztikus online algoritmusok Az algoritmusok hagyományos módon való tervezésekor feltesszük, hogy az algoritmus birtokába kerül az összes bemeneti adatnak, még miel®tt a kimeneti adatokat meg kéne adja nekünk. Sok valós alkalmazásban ez a feltételezés nem állja meg a helyét, ilyenkor az algoritmusunk még az el®tt el kell kezdje a kimenet generálását, miel®tt a teljes bemenetet ismerné. Az általunk tárgyalt online feladatok felfoghatók kérelem-válasz-játékként.
2.1.1. De níció. (Kérelem-válasz-játék) A kérelem-válasz-játék egy R kérelemhalmazból, egy véges A válaszhalmazból, és az fn : Rn ×An → R∪{∞}, n ∈ N költségfüggvényekb®l áll. Minden n-re valamely Fn ⊆ An halmazt hívjunk a megengedett válaszok halmazának. [ Legyen f := fn . n∈N
2.1.2. De níció. Egy n hosszú r kérelemsorozat költségét jelölje c(r) := min{fn (r, a)|a ∈ Fn }. Ha az r ∈ Rn kérelem- és a ∈ Fn válaszsorozatok esetén fn (r, a) = c(r), akkor az a
válaszsorozatot optimálisnak nevezzük az r-re. El®ször tekintsük a determinisztikus online algoritmusokat, azaz az olyanokat, melyek futásuk során nem használnak véletleneket.
2.1.3. De níció. (Determinisztikus online algoritmus) Egy
G determinisztikus on-
line algoritmus egy gi : Ri → A, i ∈ {1, 2, . . . } alakú függvényekb®l álló sorozat. Egy r = (r1 , . . . , rn ) kérelemsorozat esetén de niáljuk a G(r) = (a1 , . . . , an ) ∈ Fn válaszsorozatot, ahol ai = gi (r1 , . . . ri ), i ∈ {1, . . . n}. Legyen G költsége r-en cG (r) = fn (r, G(r)).
13
Online feladatok és online algoritmusok környezetében a jobb megkülönböztethet®ség érdekében a hagyományos feladatok és algoritmusok elnevezését néha kiegészítjük az o ine jelz®vel. Az online algoritmusok hatékonyságát az összehasonlító-analízis segítségével mérjük, ahol az online algoritmus által adott kimenetet hozzámérjük az optimális kimenethez.
2.1.4. De níció. (Determinisztikus online algoritmus c-közelít®sége) Legyen
α :
R → R lineáris függvény. Azt mondjuk, hogy egy G determinisztikus online algoritmus α-
közelít®, ha bármely r kérelemsorozatra cG (r) ≤ α(c(r)) teljesül. Amennyiben α(x) = dx+e, ahol d > 0, azt mondjuk, hogy a közelítési hányados d.
2.1.5. Megjegyzés. ként a
Amennyiben egy
G
algoritmus
α-közelít®,
és
α(x) = dx + e,
eseten-
G algoritmust d-közelít®nek mondjuk. Hasonló átfogalmazásokat lehet eszközölni az
α-közelít®ségek
kés®bbi de nícióinál is.
Néhány példa online feladatra:
2.1.6. Példa.
Feladatelosztás. Feladatok egy sorát kell beosztani gépek egy halmazán,
egy adott célfüggvényt optimalizálva (például az utolsónak befejezett feladat befejezési id®pontját minimalizálva). A feladatok egyenként érkeznek, és azonnal hozzá kell rendelni ®ket egy géphez, a kés®bbi feladatok ismerete nélkül. Az utolsó befejezési id®pont minimalizálását kérelem-válasz-játékként a következ®képp
M
fogalmazhatjuk meg. Legyen maza. Legyen
A = M,
tunkat. Ekkor
fn = max
2.1.7. Példa.
a gépek,
R
pedig a lehetséges feladatok id®igényének hal-
azaz a válasz azt határozza meg, melyik géphez rendeljük a felada-
m∈M
X
ri .
ai =m
Adatszerkezetek. Szeretnénk egy adatszerkezetet (pl. egyszeresen láncolt
listát, fát) karbantartani úgy, hogy minél kisebb költséggel hozzáférjünk a kért adatelemhez. A jöv®beli kéréseket nem ismerjük el®re. Lista-karbantartás. Legyen a lista hossza kérelemhalmaz. Legyen
L = {[a, b] a
és
b
k
és
R = {R1 , . . . , Rk }
a lista elemeinek egy-egy permutációja}, azaz
a lista lehetséges megváltoztatásainak halmaza. Legyen toztatások halmaza. Az
a lista elemeib®l álló
A = {1, . . . , k} × M
M ⊆ L
L
a megengedett megvál-
válaszhalmaz elemeinek els® koordinátái azt
mondják meg, hogy hányadik helyen érhet® el a kért elem, a második koordináta pedig hogy az adott állapotból milyen sorrendbe rendezi át az algoritmusunk a listát az aktuális lépésben. Legyen
fn (r, a) =
k X
al,1 ,
azaz az
n.
l=1 elérésekor.
14
kérésig tett lépések száma az adatelemek
A fa karbantartásának leírása hasonló a listáéhoz. A különbség az
M
leírásában van. A lista esetéb®l kiindulva legyen halmaza. Legyen
N
válaszhalmaz
a fa megengedett megváltoztatásainak
az összes lehetséges elérési útvonal halmaza.
ai,1 -ben tároljuk a kért elem k X al,1 módon alakulnak.
A
A = {1, . . . , k} × M × N ,
szintjét a fában. Így a költségfüggvények szintén
fn (r, a) =
l=1
2.1.8. Példa.
Memória-kezelés, azaz a számítógépek memóriájának kezelése, ahol a me-
mória egy kicsi gyors, és egy nagy lassú részb®l áll. Konkrétabb példaként, mialatt a felhasználó önkényesen lapozgat, az a célunk, hogy a gyakran látogatott oldalak a gyors memóriában legyenek tárolva, minél kevesebbszer kelljen új oldalt betölteni oda. A lapozási feladat leírásához képzeljük azt, hogy a
k
helyezkedik el egy lista els® oldal száma legyen
l.
Ekkor
k
oldalt tárolni tudó gyorsmemória
helyén, a lassú memória pedig mögötte. Az összes kezelt
R = {R1 , . . . , Rl }
az oldalakból mint a lista elemeib®l áll.
M
elemei a helybenhagyás és az olyan transzpozíciók, ahol a kicserélt elemek közül pontosan
A = {1, . . . , l} × M . A válaszok fn (r, a) := {ai,1 |ai,1 > k} .
egy van a gyorsmemóriában. Legyen tároljuk a kért elem helyét. Ekkor
2.1.9. Példa.
els® koordinátáiban
Szindbád esete a háremhölgyekkel. Mivel Szindbád nem ismeri el®re a szerre
elhaladó hölgyek szépségét, a legszebb hölgy kiválasztása számára online feladat. (A kiválasztott háremhölgy szépsége várható értékének maximalizálása szintén.) Egy lehetséges megfogalmazás a kérelem-válasz-játékok nyelvén. Tegyük fel, hogy a háremhölgyek száma ismert,
n
. Közülük az
azt a kérdést, hogy óhajtja-e Szindbád a
j
i-edik
j.
a legszebb (i
hölgyet. A
j.
∈ {1, . . . , n}).
Jelölje
rj
hölgy megjelenésekor az els®
hölgy szépsége között ismert egy rendezés, legyen ez bekódolva az
rj
kérésbe. Legyen
A = {1, 0}, azaz a lehetséges válaszok az igen és a nem. Az egyszer¶ség kedvéért tegyük fel, hogy az
r
vektor
n
koordinátából áll, azaz minden esetben az összes háremhölgy elvonul
Szindbád el®tt. Legyen a
k
hosszú megengedett válaszsorozatok halmaza
Fk = {a a ∈
Ak , ha, ai ≤ 1}. Mivel egyértelm¶, hogy Szindbád sikerrel jár vagy kudarcot vall, de niáljuk a költségfüggvényeket a következ®képp. Legyen
0 fn (r, a) = 1
ha
fm
ai = 1
különben.
15
és
azonosan nulla minden
a
megengedett,
m
esetén,
2.2. Példa: lapozási feladat A következ®kben közelebbr®l vizsgálunk egy online példát.
2.2.1. Példa. (Lapozási feladat)
Vegyük a memóriáról szóló 2.1.8 példát. Tegyük fel,
hogy a gyors memóriaegység egyszerre
k
oldalt tud tárolni, a lassú kapacitása pedig bár-
milyen nagy lehet. A kérelmek egy-egy oldal megjelenítésére szólnak. Ha az oldal a gyors memóriában található, a kérelmet kiszolgáljuk, ha pedig a lassúban van, akkor hibát jelzünk. Ebben az esetben a gyors memóriából át kell helyezni egy oldalt a lassúba, hogy a megürült helyre betölthessük a kért oldalt. Egy lapozó-algoritmus eldönti, hogy hiba esetén melyik oldalt vegyük ki a gyors memóriából. A minimalizálandó költség a jelzett hibák száma. A lapozási feladatot oldja meg a következ® két determinisztikus online algoritmus.
2.2.2. De níció. A lapozási feladatra adott
LRU (legkevésbé használt, Least Recently
Used) determinisztikus online algoritmus hibajelzéskor azt az oldalt veszi ki a gyors memóriájából, amelyik legutóbbi kérése a legrégebb történt.
2.2.3. De níció. A lapozási feladatra adott
F IF O(First-In First Out) determinisztikus
online algoritmus hibajelzéskor a gyorsmemóriában legrégebb óta bent lev® oldalt veszi ki.
2.2.4. De níció. A lapozási feladatra adott
M IN o ine algoritmus hibajelzéskor azt az
oldalt veszi ki a gyorsmemóriából, amelyik kérése a jöv®ben legmesszebb fog történni.
2.2.5. Tétel. [5] A M IN optimális. Legyen az
A
nA
az
A algoritmus gyors memóriájában tárolható oldalak száma. Jelölje FA (s)
algoritmus által az
s
bemeneten elkövetett hibák számát.
2.2.6. Tétel. Legyen A egy lapozási feladatra adott tetsz®leges determinisztikus online algoritmus. Feltéve, hogy nA ≥ nM IN , létezik tetsz®legesen hosszú s kérelemsorozat úgy, hogy FA (s) ≥ (nA /(nA − nM IN + 1))FM IN (s).
Bizonyítás. a
M IN
csak
Alkotunk egy olyan
nA hosszú kérelemsorozatot, melyen A nA hibát vét, míg,
(nA − nM IN + 1)-et.
melyek sem az
A,
sem a
mindkét algoritmus
M IN
(nA − nM IN + 1)
kérés érkezzen olyan odalakra,
gyors memóriájában nincsenek benne, így ebben a fázisban
(nA − nM IN + 1)
eredetileg benne voltak a kérés között. Ekkor
Az els®
M IN
hibát vét. Legyen
S
azon oldalak halmaza, melyek
memóriájában, vagy szerepeltek az els®
|S| = nA + 1
gyors memóriájában. A következ®
(nA − nM IN + 1)
, azaz létezik olyan eleme, ami pillanatnyilag nincs
nM IN − 1
kérés érkezzen olyan
16
S -beli
A
oldalakra, melyek
pillanatnyilag nincsenek felében mind az
A
nM IN − 1
gyors memóriájában. Ezáltal míg esetben hibát vét, a
memóriájában tartja az utolsó kérelemsorozat alatt az
A
nM IN − 1
M IN
kért oldalt. Összegezve, mialatt eme
M IN (nA − nM IN + 1)
végig hibázik, a
hosszú kérelemsorozat készíthet® úgy, hogy az Az el®z® tételbe
lapozási feladat megoldására
c
A
nA
hosszú
hibát vét. Az el®bbi
nA < nM IN ,
A bizonyításból látszik, hogy ha
2.2.8. Következmény.
a kérelemsorozat második
a leírásából adódóan sosem, hiszen
eljárást kell®en sokszor ismételve kapjuk a tétel állítását.
2.2.7. Megjegyzés.
A
M IN
mindig hibázzon, a
k := nA = nM IN -t
akkor tetsz®legesen pedig sose.
írva azt kapjuk, hogy a
esetén nem létezik c-közelít® determinisztikus online
algoritmus.
2.2.9. Tétel. Bármely s kérelemsorozatra FLRU (s) ≤ (nLRU /(nLRU − nM IN + 1))FM IN (s) + nM IN .
Bizonyítás.
Az els® kérelem után bizosan van az
oldal, mégpedig a legutóbb kért. Legyen
s
els® elemét, és amely folyamán az
el®tt kért oldalt. Ha
t-nek
folyamán legalább
Osszuk
s-et
legfennebb
M IN
fel
s0 , s2 , . . . , sk -ra,
LRU .
hibázik. Jelölje
p
a közvetlen
Ekkor
legalább
nLRU + 1
úgy, hogy
különböz® oldalra. Ugyanez igaz, ha
és az
LRU
s0
mindegyikén az
si -n
esetén pedig
LRU
és a
M IN
alatt amennyiben az
pontosan
nLRU
hibáinak aránya
LRU f0 -szor hibázik,
ejt hibát. Mindent összevetve kapjuk a tételt.
A tételben szerepl® additív tag abból adódik, hogy kezdetben a
gyors memóriájában teljesen különböz® oldalak szerepelhetnek. Ezt a
M IN
LRU
gyors memóriájában
gyors memóriájának összes eleme, és ezeknél frissebben nem volt
használva egyetlen más elem sem.
2.2.11. Tétel. Amennyiben nLRU Bizonyítás.
miatt
tartalmazza az els® kérést és legfennebb
tagot eltüntethetjük azáltal, hogy feltesszük, hogy kezdetben az megtalálható a
p-n
hibázik.
LRU , i ∈ {1, . . . , k}
s1 , . . . , s k
f0 − nM IN -szer
t
kétszer is hibázik ugyanazon oldal kérésekor, akkor
nLRU /(nLRU − nM IN + 1). Ekkor s0
2.2.10. Megjegyzés. M IN
memóriájában közös
egy olyan részsorozata, mely nem tartalmazza
f − nM IN + 1-szer
hibát kövessen el rajta az
hibát ejtsen az
a
LRU
M IN
t alatt. Ha az el®bbi két eset közül egyik sem következik be, akkor f ≤ nLRU
M IN t
nLRU
alatt az
és a
LRU f ≤ nLRU -szor
tartalmazni kell kérést legalább
hibázik a
t
ts
LRU
= nM IN =: k , az LRU k-közelít®.
Felhasználva 2.2.8-t, és 2.2.9
nLRU = nM IN
2.2.12. Tétel. Amennyiben nF IF O = nM IN
esetét, a tételt kapjuk.
=: k , a F IF O k-közelít®.
17
2.3. Véletlen online algoritmusok Egy természetesen felmerül® kérdés, hogy érhetünk-e el jobb eredményt nemdeterminisztikus algoritmusokat használva. Ennek megválaszolásához de niálni kell a randomizált online algoritmusok c-közelít®ségét.
2.3.1. De níció. (Véletlen (randomizált, véletlenített) online algoritmus) Legyen D determinisztikus online algoritmusok egy halmaza, P egy eloszlás D-n, ahol minden d ∈ D esetén P (d) annak az esélye, hogy d fut le. Ekkor a G(D, P ) párost véletlen online
algoritmusnak hívjuk.
2.3.2. Megjegyzés. gyakran
G-vel
Az egyszer¶ség kedvéért egy
jelölünk. Bármely
r
G(D, P )
kérelemsorozatra a
G(r)
véletlen online algoritmust válaszsorozat, így a
cG (r)
költség is valószín¶ségi változó.
2.3.3. Állítás. Legyen
G(D, P ) egy véletlen online algoritmus. Ekkor E[cG(D,P ) (r)] =
P (d)cd (r).
X d∈D
2.3.4. De níció. Egy
G véletlen online algoritmust valamely α lineáris függvény esetén
α-közelít®nek hívunk, ha bármely r bemeneti sorozatra E[cG (r)] ≤ α(c(r)). Mivel a c-közelít®ség szempontjából fontos, hogy a vizsgált algoritmusunk minden
r
kérelemsorozaton jól teljesítsen, gondolhatunk arra, hogy a bemenetet egy ellenség szolgáltatja. A következ® típusú ellenfeleket szokás vizsgálni:
2.3.5. De níció. (Feledékeny ellenfél) A feledékeny ellenfél (oblivious adversary) legenerálja a teljes r kérelemsorozatot, még miel®tt az online algoritmus kielégített volna egyetlen kérelmet is. A feledékeny ellenfél ismeri az általa generált kérelemsorozat optimális megoldását, így az ® költsége c(r). Az alkalmazkodó o ine ellenfél (adaptive o ine adversary) meg gyelheti az online algoritmust, és a következ® kérelmet adhatja az eddigi kérelmekre kapott válaszok alapján. A kérelemsorozatot optimális módon teljesíti.
2.3.6. De níció. (Alkalmazkodó o ine ellenfél) Egy Q alkalmazkodó o ine ellenfél egy qk : Ak → R ∪ {stop} függvénysorozat, ahol dQ ∈ N, k ∈ {1, . . . , dQ } és qdQ csak a stop értéket veheti fel. Egy G determinisztikus online algoritmus és Q alkalmazkodó ellenfél esetén legyen r(G, Q) = (r1 , . . . , rn ) a tényleges kérelemsorozat, a(G, Q) = (a1 , . . . , an ) a tényleges válaszsorozat, n ≤ dQ ezek hossza. Ezen objektumokat a következ®kben leírtak szerint, egyenként számoljuk ki, a következ® sorrendben: r1 , a1 , r2 , a2 , . . . , rn , an , n. 18
Legyen ri+1 := qi (a1 , . . . , ai ), i ∈ {0, . . . , n−1}, a(G, Q) := G(r(G, Q)) és qn (a(G, Q)) = stop. A G algoritmus költsége a Q ellenfél esetén legyen cG (Q) := fn (r(G, Q), a(G, Q)). A Q ellenfél költsége a G algoritmus esetén cQ (G) = c(r(G, Q)). Egy H(D, P ) véletlen online algoritmus esetén r(H(D, P ), Q), a(H(D, P ), Q) és n = n(H(D, P ), Q) valószín¶ségi változók. Ekkor a H(D, P ) algoritmus várható költsége a Q X ellenfél esetén E[cH(D,P ) (Q)] = P (d)cd (Q). A Q ellenfél várható költsége a H(D, P ) d∈D
algoritmus esetén E[cQ (H(D, P ))] =
X
P (d)cQ (d).
d∈D Az alkalmazkodó online ellenfél az alkalmazkodó o ine ellenfélhez hasonló, azzal a különbséggel, hogy minden kérelmet online kell teljesítsen, azaz nem ismeri az algoritmus által a jelenben és jöv®ben adott (véletlen) válaszokat.
2.3.7. De níció. (Alkalmazkodó online ellenfél) Egy
S = (Q, P ) alkalmazkodó on-
line ellenfél egy alkalmazkodó o ine ellenfél, ellátva egy P = {p1 , . . . , pn } függvénysorozattal, ahol pk : Ak → A, k ∈ {1, . . . , dQ }. Legyen G egy determinisztikus online algoritmus. Mivel r(G, S) független P -t®l, r(G, S) = r(G, Q), a(G, S) = a(G, Q) és cG (S) = cG (Q). Az S alkalmazkodó online ellenfél válaszsorozata b(G, S) = (b1 , . . . , bn ), ahol n := n(G, Q) és bi+1 = pi (a1 , . . . , ai ), i ∈ {0, . . . , n − 1}. Legyen S költsége G esetén cS (G) = fn (r(G, S), b(G, S)). Az el®bbi de nícióhoz hasonlóan egy S véletlen online algoritmus esetén E[cS (H(D, P ))] = X P (d)cS (d). d∈D
2.3.8. Megjegyzés.
Determinisztikus online algoritmust tekinthetünk speciális randomi-
zált online algoritmusnak. Figyeljük meg, hogy ebben az esetben a három ellenfélfogalom egybeesik: mindhárom annyit tehet, hogy megválasztja a bemenetet. Ezért a 2.1.4 de nícióból adódóan determinisztikus online algoritmusnál a c-közelít®ség szempontjából mindegy, hogy használjuk-e bármely ellenfelet, vagy sem.
2.3.9. De níció. (α-közelít®ség feledékeny ellenfelekhez) Egy G véletlen online algoritmus α-közelít®sége bármely feledékeny ellenfélhez jelentse ugyanazt, mint a 2.3.4-ben leírt α-közelít®sége.
2.3.10. De níció. (α-közelít®ség alkalmazkodó o ine ellenfelekhez) Egy G véletlen online algoritmust α-közelít®nek nevezünk bármely alkalmazkodó o ine ellenfélhez, ha bármely Q alkalmazkodó o ine ellenfél esetén E[cG (Q)] ≤ E[α(cQ (G))].
19
2.3.11. De níció. (α -közelít®ség alkalmazkodó online ellenfelekhez) Egy A randomizált online algoritmus α-közelít®nek nevezünk bármely alkalmazkodó online ellenfélhez, ha bármely S alkalmazkodó online ellenfél esetén E[cG (S)] ≤ E[α(cS (G))].
2.3.12. Megjegyzés. tén
a ≥ 1.
A költségminimalizáló feladatból adódik, hogy
α(x) = ax + b
ese-
Azonban amennyiben a feladatunk valamely célfüggvény maximalizálása, az
α-közelít®ségeket
értelemszer¶en újrade niáljuk, ekkor
a≤1
lesz. A rájuk vonatkozó, ér-
telemszer¶en átfogalmazott állítások igazak maradnak. A következ®kben rangsoroljuk az ellenfeleket.
2.3.13. Tétel. [3] Ha létezik minden alkalmazkodó o ine ellenfelet α-közelít® véletlen online algoritmus, akkor létezik minden alkalmazkodó o ine ellenfelet α-közelít® determinisztikus online algoritmus is.
2.3.14. Következmény.
Az alkalmazkodó o ine ellenfelet ugyanannyira lehet közelíteni
determinisztikus online algoritmussal, mint véletlen online algoritmussal.
Az el®bbi tétel üzenete az, hogy az alkalmazkodó o ine ellenfél jobb közelítésében nem segít a randomizálás.
2.3.15. Állítás. Legyen G egy véletlen online algoritmus. Ha G b-közelít® bármely alkalmazkodó online ellenfélhez, akkor b-közelít® bármely feledékeny ellenfélhez is.
Bizonyítás.
Minden feledékeny ellenfelet utánozni lehet alkalmazkodó online ellenféllel.
2.3.16. Tétel. [3] Legyen G egy véletlen online algoritmus. Ha G b-közelít® bármely alkalmazkodó online ellenfélhez, és c-közelít® bármely feledékeny ellenfélhez, akkor (b ·c)-közelít® bármely alkalmazkodó o ine ellenfélhez.
2.3.17. Következmény.
Legyen
G
egy véletlen online algoritmus. Ha
mely alkalmazkodó o ine ellenfélhez, és
c-közelít®
Bizonyítás.
b-közelít®
bár-
bármely alkalmazkodó online ellenfélhez,
bármely feledékeny ellenfélhez, akkor 2.3.15-b®l és 2.3.16-ból következik.
G a-közelít®
a ≥ b ≥ c.
Miel®tt az eredményeket összefoglalnánk, az ellenfeles környezet mellett ejtsünk pár szót a sztochasztikus esetr®l is, amikor a kérelmek véletlenszer¶en érkeznek.
2.3.18. De níció. (Sztochasztikus kérelemsorozat) Legyen
n egy valószín¶ségi vál-
tozó, mely a {0, . . . N }, N ∈ N értékeket veheti fel. Legyen rn = (ρ0 , . . . , ρn ) olyan valószín¶ségi változók egy vektora, a valószín¶ségi változók értékkészlete az R kérelemhalmaz egy részhalmaza. Ekkor az rn kérelemsorozatot sztochasztikusnak nevezzük. 20
2.3.19. De níció. (sztochasztikus α-közelít®ség) Egy G(D, P ) algoritmust egy rn sztochasztikus kérelemsorozat és α lineáris függvény esetén sztochasztikusan α-közelít®nek nevezünk (az optimumhoz), ha E[cG (rn )] ≤ α(E[c(rn )]), ahol a várhatóértéket rn és P szerint vesszük.
2.3.20. Állítás. Ha egy G online algoritmus α-közelít® minden feledékeny ellenfélhez, akkor sztochasztikusan is α-közelít®.
Bizonyítás.
Az, hogy a
G(D, P )
online algoritmus
félhez, azzal ekvivalens, hogy bármely b®l következik, hogy bármely
α(E(rn ,P ) [c(r)]),
azaz
G
rn
r
α-közelít®
minden feledékeny ellen-
EP [cG (r)] ≤ α(c(r)).
bemeneti sorozatra
E(rn ,P ) [cG (r)] ≤
sztochasztikus kérelemsorozat esetén
sztochasztikusan
Eb-
α-közelít®.
2.3.21. Állítás. Ha létezik sztochasztikusan α-közelít® G(D, P ) véletlen online algoritmus, akkor létezik sztochasztikusan α-közelít® H determinisztikus online algoritmus is.
Bizonyítás.
G(D, P )
sztochasztikus
α-közelít®sége
a következ®t jelenti:
E(rn ,P ) [cG (rn )] ≤ α(E(rn ,P ) [c(rn )]), ami a 2.3.3 állítás alapján az egyel®tlenség a következ® alakba írható:
Er n
X
P (d)cd (r) ≤ α(Ern [c(rn )]).
d∈D A legutóbbi egyenl®tlenség csak akkor állhat fenn, ha létezik olyan online algoritmus, amire
d∈D
determinisztikus
Ern cd (rn ) ≤ α(Ern [c(rn )]).
2.3.22. Következmény.
Sztochasztikus esetben ugyanannyira lehet közelíteni az optimu-
mot determinisztikus online algoritmussal, mint véletlen online algoritmussal.
A fentebb bemutatott eredményeket az alábbi táblázatban tekinthetjük át, ahol az
(i, j)
helyen található szám az
i
típusú online algoritmussal bármely
j
típusú ellenfél el-
len, illetve sztochasztikus esetben elérhet® legjobb közelítési hányados. A determinisztikus eset összes ellenfeles mez®jét egyesítettem, mivel
c-közelítési
fogalmak ezekben egybees-
nek. Megjegyezend®, hogy az ellenfél nélküli és feledékeny ellenfeles esetek de níció szerint ugyanazt jelentik, így az ellenfél nélküli eredményeket a feledékeny ellenfeles oszlopból lehet kiolvasni.
21
Sztochasztikus Determinisztikus
d
Véletlen
d
Feledékeny
Alkalmazkó online
Alkalmazkodó o ine
a b
c
a
2.1. táblázat. Az online költségminimalizálási feladatban determinisztikus és véletlen online algoritmusokkal a különböz® ellenfelekkel szemben, illetve a sztochasztikus esetben elérhet® legalacsonyabb közelítési hányadosok. Itt
d≤c≤b≤a
és
a ≤ cb.
2.4. Példa: maximális párosítás online keresése Ebben az alfejezetben f®ként a [6] cikk tartalmát dolgozzuk fel. Sok, a Szindbád-feladathoz köthet® problémát meg lehet fogalmazni. Egy számunkra érdekes kérdés az online házasításé, azaz a páros gráfokban történ® maximális párosítás keresése. Látni fogjuk, hogy itt különböz® típusú ellenfelekhez más-más közelítési eredményeket érhetünk el. A feladat leírása a következ®. Legyen
H(U, V, E)
egy
2n
ponton értelmezett teljes párosítást tartalmazó páros gráf,
ahol két pont között pontosan a kölcsönös szimpátia esetén van él. Legyen mátrix, melyben eltároljuk a hoz ( úk), oszlopai a
V -beli
H
B
szerkezetét. A mátrix sorai tartozzanak az
pontokhoz (lányok),
Szeretnénk minél nagyobb párosítást készíteni
Bi,j := 1,
ha
egy
{0, 1}n×n
U -beli
{Ui , Vj } ∈ E ,
pontok-
különben 0.
H -ban online módon. Tegyük fel, hogy a ú
pontok jelen vannak, a lány pontok pedig egy el®re meghatározott sorrendben érkeznek, és a hozzájuk tartozó élek az érkezésükkor kerülnek birtokunkba. A feladatunk eldönteni minden érkez® lány pontra, hogy melyik ú ponthoz adjuk (ha adjuk) úgy, hogy minél nagyobb párosításhoz jussunk. Az ezzel ekvivalens feladatot megfogalmazhatjuk a
B mátrixra
is, ahol a oszlopok (melyek a lányokhoz tartoznak) a lányok érkezési sorrendjénak függvényében szerre válnak ismertté. Legyen ez a sorrend
σ = Bσ1 , . . . , Bσn .
Az általánosság
megszorítása nélkül megváltoztathatjuk az oszlopok mátrixon belüli helyét. Ezentúl feltételezzük, hogy
A(H)
σ = Bn , Bn−1 . . . , B1 .
valószín¶ségi változó az
A
Egy
A
randomizált online algoritmus esetén legyen
algoritmus által
H
bemeneten konstruált párosításának
elemszáma.
2.4.1. De níció. Az online párosítási feladatban az el®bbiekben leírt jelölések mellett az A randomizált online algoritmus teljesítményét a p(A) := min E[A(H)] módon értelmezzük, H ahol a várhatóértéket az A által használt véletleneken vesszük.
2.4.2. Állítás. A párosítási feladatra létezik 1/2-közelít® mohó determinisztikus online algoritmus, és nem létezik olyan determinisztikus online algoritmus, mely (1/2 + )-közelít® 22
lenne (tetsz®leges ellenfélhez), semely > 0 esetén.
Bizonyítás.
Egy mohó algoritmus, mely amennyiben lehet, mindig hozzáad egy lányt egy
tetsz®leges választható úhoz, minden esetben elér egy olyan párosításhoz, amelyik tovább nem b®víthet®, azaz mérete legalább
dn/2e.
Másrészt a program leírásának ismeretéb®l
adódóan egy (tetsz®leges típusú) ellenfél bármely determinisztikus online algoritmus által elért legnagyobb párosítás méretét korlátozni tudja megjelen®
dn/2e
oszlopba
1-eseket
determinisztikus algoritmus az els®
2.4.3. Megjegyzés.
ír, a maradékban pedig csak azokba, amelyikeket a
dn/2e
lépésben párosított.
>0
Az el®bbi állítás és a 2.3.14 értelmében véletlen online algoritmussal
minden alkalmazkodó o ine ellenfelet lehet semmilyen
dn/2e-ben, például úgy, hogy az els®nek
1/2-közelíteni, és nem lehet(1/2 + )-közelíteni
esetén.
2.4.4. Állítás. Randomizált online angoritmusok által generált párosítások várható méretének egy alkalmazkodó online ellenfél n/2 + O(log n)-es fels® korlátot tud szabni. Azaz nem létezik alkalmazkodó online ellenfélhez (1/2+)-közelít® randomizált online algoritmus, semmilyen > 0 esetén.
Bizonyítás. esetén
Az ellenfél konstruálja
B -t
a következ® módon. Adott
i ∈ {0, . . . , dn/2e}
Bj,n−i = 1 pontosan akkor, ha a j . sor nem eleme sem az algoritmus, sem az ellenfél
által eddig készített párosításnak sem; az ellenfél a saját teljes párosításához egy tetsz®leges
1-est választ az aktuális (n−i). oszlopból. i ∈ {dn/2e+1, . . . , n} esetén Bj,n−i = 1 pontosan akkor, ha a
j . sor nem eleme az ellenfél által eddig készített párosításnak; az el®bbi esethez
hasonlóan az ellenfél a saját teljes párosításához egy tetsz®leges
(n − i).
1-est
választ az aktuális
oszlopból.
Hogy ezen ellenség ellen randomizált online algoritmus nem érhet el
n/2 + O(log n)-nél
nagyobb párosítást, a következ®k miatt igaz. Egyrészt minden nem mohó randomizált online algoritmus (azaz mely nem feltétlenül rendel hozzá út a lányhoz, mikor erre lehet®ség van) lecserélhet® olyan mohóra (mely minden lehet®ségkor hozzárendel a lányhoz út), mely legalább ugyanolyan jól teljesít átlagosan. Másrészt, bármely legyen
T (A)
A
mohó algoritmusra
Bn , Bn−1 , . . . , Bbn/2c oszlopok va Ekkor E |T (A)| = O(log n), és az A
azon sorok halmaza, melyeket párosított a
lamelyikével mind az algoritmus, mind az ellenfél.
által konstruált párosítás mérete nem haladja meg az
n/2 + |T (A)|
számot.
Az alkalmazkodó ellenfél vizsgálata után nézzük, mit mondhatunk feledékeny ellenfél esetén.
2.4.5. De níció. A RANKING egy, az online párosításra adott algoritmus, mely két fázisból áll: 23
Inicializálás: A ú pontokat rendezzük véletlenszer¶en, nevezzük ezt a sorrendet rangnak. Párosítás: Ahogy megérkezik egy lány pont, rendeljük a legmagasabb rangú elérhet® ú ponthoz (amennyiben létezik ilyen).
2.4.6. Megjegyzés.
Elég természetesnek t¶nik egy még egyszer¶bb algoritmust tanulmá-
nyozni, ami az érkez® lány pontot egy tetsz®leges elérhet® ú ponthoz rendeli, ez azonban a teljes fels®háromszög-mátrixon várhatóan Ehhez képest a
RAN KIN G
n/2+O(log n) méret¶ párosítást fog produkálni.
éppen a ú pontok rangsorolása miatt másként viselkedik,
implicit módon el®nyben részesítve azokat a úkat, melyek kevésbé voltak választhatók a múltban.
2.4.7. Tétel. [7] A
B mátrixhoz tartozó teljes párosítást tartalmazó 2n pontú gráfban,
a RAN KIN G által adott párosítás várható mérete legalább (1 − 1/e) + o(n). Tehát a RAN KIN G (1 − 1/e)-közelíti bármelyik feledékeny ellenfelet.
2.4.8. Tétel. [7] > 0 esetén nem létezik minden feledékeny ellenfelet (1−1/e+)-közelít® online maximális párosítást keres® algoritmus. Az el®bbiek alapján felvázolhatjuk a következ® táblázatot. Ahol a fogalmak egybeesnek, a mez®k egyesítettek. Feledékeny
Alkalmazkó online
Determinisztikus
1/2
1 − 1/e
Véletlen
Alkalmazkodó o ine
1/2
1/2
2.2. táblázat. Jelen feladatban determinisztikus és véletlen online algoritmusokkal a különböz® ellenfelekkel szemben elérhet® legmagasabb közelítési hányadosok.
Mint látható, bár a véletlen online algoritmusoknak elvileg lehet®ségük van magasabb közelítési hányadost elérni a determinisztikusoknál, az alkalmazkodó online ellenfélnél tapasztalt
O(log n)-es
többlet még nem jelentkezik a közelít®ség mértékében. Így a determi-
nisztikus és véletlen algoritmusok hatékonysága jelen feladatban a feledékeny ellenfeles és ellenfél nélküli esetben különbözik lényegesen.
2.4.9. Megjegyzés.
Az online maximális párosítás keresésének feladata felfogható szub-
moduláris függvények összegének online maximalizálásaként is, így felfoghatjuk a következ® fejezetben tárgyalt probléma egy sajátos eseteként. Képzeljük ugyanis az eddigi az ügynökök,
V
H(U, V, E)
páros gráfot úgy, hogy egy árverésen
elemei pedig a tárgyak, és minden
24
i ∈ U
ügynök a
U
j ∈ N (i)
elemei
tárgyak
közül pontosan egy darab megszerzésében érdekelt, azaz az
wi (S) := min{S ∩ N (i)}
i ügynök hasznossági függvénye
alakban írható. Könnyen ellen®rizhet®, hogy minden
i ∈ U -ra wi
szubmoduláris. Így ebben a megfogalmazásban a feladatunk az ügynökök összhasznának maximalizálása.
25
3. fejezet
Online szubmoduláris árverések 3.1. Online szubmoduláris árverések A
2.4 részben tárgyalt feladat vizsgálata indította el a tudományos munkák azon sorozatát,
amibe illeszkedik az alább meghatározott online szubmoduláris kombinatorikus árverési feladat is. Gyakorlati alkalmazásai az árveréseken és online hirdetési felületeken kívül számos helyen elképzelhet®k.
3.1.1. De níció. (Online szubmoduláris kombinatorikus árverési feladat) Tekintsünk egy árverést, ahol |T | = t darab, el®re ismeretlen tárgy érkezik egyenként, amiket érkezésük pillanatában hozzá kell rendeljünk az u darab ügynök valamelyikéhez. Azt, hogy tárgyak egy halmaza milyen hasznot hoz az i. ügynöknek, a wi : 2T → R+ alakú, haszonfüggvénynek nevezett szubmoduláris hozzárendelés adja meg. Feladatunk a lizálása, ahol Si az i. ügynökhöz rendelt tárgyak halmaza, alkotja.
3.1.2. Megjegyzés.
u X
wi (Si ) kifejezés maximai=1 azaz S1 , . . . , Su S egy partícióját
A maximalizálandó kifejezés azt méri, hogy az ügynökök összessé-
gének mennyire hasznos a tárgyak elosztása. Ez indokolhatja az árverési feladat angol szakirodalomban gyakran használatos
welfare maximization
elnevezést.
Feltesszük, hogy mindenki együttm¶ködik (szeretné a közjót növelni), így nem foglalkozunk a feladat játékelméleti vonatkozásaival. Akárcsak az
1
fejezetben, itt is feltesszük, hogy a szubmoduláris függvények értékeit
egy orákulum kérésünkre azonnal szolgáltatja.
26
3.2. Ellenféllel szemben Ebben az alfejezetben célunk olyan algoritmus keresése, amely minden, a futása el®tt rögzített bemeneten jól teljesít. Látni fogjuk, hogy a mohó algoritmusok sok esetben az árverési feladatokban is hatékonynak bizonyulnak.
3.2.1. De níció. (Mohó algoritmus) A mohó algoritmus egy árverési feladatban az érkez® tárgyat a legkisebb sorszámú olyan ügynökhöz rendeli, amelynek legnagyobb haszna származik bel®le.
3.2.2. Tétel. [8] A mohó algoritmus online szubmoduláris árverési feladatokban 1/2-közelít®, amennyiben a haszonfüggvények monotonok.
Bizonyítás.
Jelölje
Q
az eredeti feladatunkat, ahol
t
tárgy érkezik
Tegyük fel, hogy az els® tárgyat a mohó algoritmus a
Q0 -tel
azt a feladatot, amit a
Q-ból
:= ∆wj (S|{1})
függvényre. Legyen
keletkezett összhasznát az ügynököknek,
p=
Legyen
S1 , . . . , Su
j.
ügynök
´ M OH O(Q)
OP T (Q)
wj ({1}). Q0 meghatározásából adódóan
z®kben megmutatjuk, hogy
ügynök részére.
ügynökhöz rendelte. Jelöljük
kapunk azáltal, hogy az érkez® tárgyak sorának ele-
jér®l elhagyjuk az els® (1 nev¶) tárgyat, és a
0 a wj (S)
j.
u
wj
haszonfüggvényét lecseréljük
a mohó algoritmus futása során
pedig az optimális összhasznot. Legyen
´ ´ 0 ) + p. M OH O(Q) = M OH O(Q
A követke-
OP T (Q) ≤ OP T (Q0 ) + 2p.
egy kiválasztott optimális elosztás, ahol
tárgyak halmazát jelöli. Tegyük fel, hogy az els® tárgy eleme zárendelésben az els® tárgy a
k -adik
ügynöknél van. Legyen
Si
az
i.
ügynökhöz rendelt
Sk -nak, azaz az optimális hozSi0
az optimális elosztásból az
0 0 0 els® elem elhagyásával keletkezett elosztás Ekkor Si = Si , minden i 6= k esetén, és S1 , . . . , Sk 0 0 egy lehetséges optimális megoldása Q -nek. Hasonlítsuk össze OP T (Q) és OP T (Q ) értékét. A
k.
esetben, a
ügynök kivételével mindegyikhez ugyanazokat a tárgyakat rendeljük mindkét
j.
ügynök kivételével pedig mindegyiknek megegyezik a haszonfüggvénye. Az
általánosság megszorítása nélkül feltehet®, hogy során a
k.
ügynök legfennebb
wk ({1})
a mohó algoritmus futása miatt értéket veszít. A
j.
k 6= j .
A
Q
feladatról a
hasznot veszít, mivel a
wk ({1}) ≤ wj ({1}) = p,
ügynök is legfennebb
p
wk
így a
hasznot veszít, mivel
Q0 -re
való áttérés
szubmoduláris, továbbá
k.
wj
ügynök legfennebb
p
monotonitásából adó-
0 0 dóan wj (Sj ) = wj (Sj ∪ {1}) − wj ({1})) ≥ wj (Sj ) − p. Így OP T (Q ) ≥ OP T (Q) − 2p. 0 A Q feladatban szerepl® haszonfüggvények szintén szubmodulárisak lesznek, így indukció segítségével nyer bizonyítást:
´ 0 ) + 2p = 2M OH O(Q). ´ OP T (Q) ≤ OP T (Q0 ) ≤ 2M OH O(Q 27
3.2.3. Megjegyzés.
Könny¶ belátni, hogy a mohó algoritmus legfennebb
1/2-közelít®,
mivel a következ® példán csak az optimum felét éri el:
∅
{1}
{2}
{1, 2}
w1
0
1
1
1
w2
0
1
0
1
Amennyiben a haszonfüggvények nem monotonok, a mohó algoritmus esetenként nagyon rosszul teljesít. Egy példa erre:
3.2.4. Megjegyzés.
∅
{1}
{2}
{1, 2}
w1
0
0
1
0
w2
0
0
0
0
A mohó algoritmus polinomiális futásidej¶.
A következ®kben megmutatjuk, hogy amennyiben létezik
1/2-nél
N P 6= RP ,
jelen feladatra nem
nagyobb közelítési hányadosú algoritmus.
3.2.5. De níció. (Fedés-kiértékelés) Egy
w : 2M → R+ függvényt fedés-kiértékel®nek
(coverage valuation) hívunk, ha létezik egy olyan {Aj : j ∈ M } halmazrendszer, amire [ w(S) = | Aj |, minden S ⊆ M esetén. j∈S
3.2.6. Állítás. A fedés-kiértékel® függvények szubmodulárisak. 3.2.7. De níció. (RP) RP-belinek mondjuk az olyan feladatokat, melyekre léteztik olyan polinomiális futásidej¶ véletlen Turing-gép, mely NEM-mel tér vissza, ha a válasz NEM, és legalább 1/2 valószín¶séggel IGEN-nel tér vissza, ha a válasz IGEN.
3.2.8. Tétel. [7] Ha
N P 6= RP , δ > 0 és fedés-kiértékel® haszonfüggvények esetén nem
létezik olyan polinomiális futásidej¶ online algoritmus, mely (1/2+δ)-közelít® lenne minden feledékeny ellenfélhez az online szubmoduláris árverési feladatban.
3.2.9. Következmény.
Ha
N P 6= RP
futásidej¶ online algoritmus, mely
δ > 0
és
(1/2 + δ)-közelít®
az online szubmoduláris árverési feladatban.
3.2.10. Megjegyzés.
esetén nem létezik olyan polinomiális lenne minden feledékeny ellenfélhez
Az eredményeket összegezve: a 3.2.2 tétel, a 3.2.9 következmény és
az ellenfelek típusainak er®sorrendje értelmében monoton szubmoduláris haszonfüggvények
28
1/2-közelít®
esetén az árverési feladatra létezik
δ > 0 esetén nem létezik olyan polinomiális futásidej¶ véletlen online
mohó), és semmilyen algoritmus, mely
determinisztikus online algoritmus (pl. a
(1/2 + δ)-közelít®
lenne minden feledékeny, minden alkalmazkodó online,
illetve minden alkalmazkodó o ine ellenfélhez, hacsak
3.2.1.
NP
RP -vel.
nem egyenl®
Azonos tárgyak esetén
Egy természetesen felmerül® kérdés az, hogy mit mondhatunk akkor, ha az árverésen minden tárgy egyforma. Ekkor minden ügynök haszna egy, csak a hozzá rendelt tárgyak számától függ® konkáv függvénnyé egyszer¶södik.
3.2.11. Tétel. [9] Azonos érkez® tárgyak esetén a mohó algoritmus az online szubmoduláris árverés egy optimális megoldását szolgáltatja.
Bizonyítás.
Minden
esetén legyen
ai,j = ∆wi (A|B), azaz az i. ügynöknek a j . tárgy által hozott haszon. Legyen
S
az összes ilyen
ai,j
szeretnénk választani
|A| = j , j ∈ {1, . . . , t}, B ⊂ A, |B| = j − 1
szám multihalmaza. Tekintsük azt a
t darabot az S
M AX
és minden
i ∈ {1, . . . u}
nev¶ feladatot, amikor ki
elemei közül úgy, hogy ezek összege maximális legyen.
Ezt megtehetjük mohó eljárással: minden lépésben az S-ben lev® elemek közül kivesszük a legnagyobbat (ha több ilyen van, akkor közülük az els®, majd a második index szerinti legkisebb sorszámút). Könnyen látszik, hogy ennek a feladatnak az optimuma fels® korlátja az árverési feladatunknak. Figyeljük meg, hogy Legyen az
wi
szubmodularitása miatt
Si = {ai,j |k ∈ {1, . . . , t}}
ai,j ≥ ai,k ,
minden
multihalmaz. Tegyük fel, hogy a
adott mohó algoritmus a legutóbbi lépésben
ai,k -t
k > j
M AX
esetén.
feladatra
választotta. Ekkor minden i-re ha az
Si
multihalmazból a következ®kben választ új elemet az algoritmus, akkor az szükségképpen az
ai,k+1 lesz, mivel a mohó eljárás leírása és ai,k k szerinti monoton csökken®sége miatt sem
kisebb, sem nagyobb index¶t nem választhat az algoritmus. Így a
M AX
feladat megoldása
megengedett megoldása lesz az eredeti árverési feladatunknak is. Megjegyezend®, hogy egy ellenfél mozgástere annyiban merül ki, hogy megválaszthatja az érkez® tárgyak számát, ez azonban nem változtat az optimalitáson.
3.2.12. Megjegyzés.
Figyeljük meg, hogy jelen esetben az optimalitáshoz nem szükséges,
hogy a haszonfüggvények monotonok legyenek.
3.2.2.
Azonos haszonfüggvények esetén
Az ellenféllel szembeni feladatnak egy másik természetesen adódó sajátos esete az, amikor az ügynökök haszonfüggvényei megegyeznek. Bár az erre a feladatra adott online algorit-
29
musok közelítési hányadosaira adhatók
1-nél
kisebb fels® korlátok, jelenleg nyitott kérdés,
hogy e feladatban mohó algoritmus milyen hatékony, illetve hogy a leghatékonyabb-e.
3.2.13. Állítás. Azonos haszonfüggvény¶ online monoton szubmoduláris árverési feladatokban a mohó algoritmus nem lehet (3/4 + δ)-közelít®, semmilyen δ > 0 esetén.
Bizonyítás. Az állítás igazolásához elég mutatni egy olyan esetet, melyben a mohó algoritmus az optimum
3/4-ét
éri el. Egy példa erre a következ®. Két ügynök részére érkezik négy
tárgy. Legyen az ügynökök halmaza
T = {A, B, C, D}, Jelölje
w:
2T
U = {u1 , u2 },
Legyen az érkez® tárgyak halmaza
a tárgyak érkezzenek a névsor szerint.
→ {0, 1, 2}
az ügynökök egymáséval megegyez® haszonfüggvényét.
Az alábbi táblázatokban a fels® sor celláin belül egymás mellé írt bet¶k jelentsék azoknak a tárgyanak a neveit, melyek halmazára alkalmazzuk a Minden
w
t∈T
esetén legyen
w
függvényt.
w({t}) = 1.
AB
AC
AD
BC
BD
CD
ABC
ABD
ACD
BCD
ABCD
1
2
2
2
1
2
2
2
2
2
2
A mohó algoritmus által adott hozzárendelések és összhasznaik körr®l-körre:
´ M OH O ¨ Osszhaszon :
1. kör
2. kör
3. kör
4. kör
1
2
3
3
u1
A
A
AC
ACD
B
B
B
u2 Egy optimális megoldás:
OP T ¨ Osszhaszon :
1. kör
2. kör
3. kör
4. kör
1
2
3
4
u1
A
A
A
BD
B
BC
BC
u2
Látható, hogy a mohó algoritmus által elért összhaszon 3, míg az optimum 4. Tehát jelen feladatban a mohó algoritmus az optimum
3/4-ét
éri el.
3.2.14. Megjegyzés.
Amennyiben a haszonfüggvény nem monoton, a mohó algoritmus
esetenként nagyon rosszul teljesít. Egy példa erre:
30
w
∅
A
B
C
AB
AC
BC
ABC
0
0
1
0
0
0
0
3.1. táblázat. Nem monoton közös haszonfüggvény esetén a mohó teljesíthet rosszul. Itt két ügynök és
&0
esetén az optimum nagyon kis részét éri el.
3.2.15. Állítás. Azonos haszonfüggvény¶ online monoton szubmoduláris árverési feladatokban δ > 0 esetén nem létezik minden alkalmazkodó o ine ellenfelet (3/4 + δ)-közelít® online algoritmus.
Bizonyítás. U = {u1 , u2 },
Vegyük a következ® feladatot. Legyen az ügynökök halmaza tárgyak halmaza hogy egy
ALG
T = {A, B, C, D}, a tárgyak érkezzenek névsor szerint. Indirekt tegyük fel,
nev¶ algoritmus valamely
o ine ellenfelet. Minden
ALG
az érkez®
X ∈ T
δ > 0-ra (3/4 + δ)-közelít
esetén legyen
minden alkalmazkodó
w({X}) = 1, w({A, B}) = 1.
Ekkor az
algoritmus szükségszer¶en nem ugyanahhoz az ügynökhöz rendeli az els® kett®nek
érkez®
A
és
B
tárgyakat. Az általánosság megszorítása nélkül tegyük fel, hogy az
az els® ügynökhöz rendeli. Legyen
w({A, C}) = w({B, C}) = 2.
megszorítása nélkül tegyük fel, hogy az
A-t
Szintén az általánosság
ALG a C -t az els® ügynökhöz rendeli. Ekkor legyen
w({A, D}) = w({A, C, D}) = 2, w({B, D}) = 1. Végezetül a 3 és 4 elem¶ halmazok haszna legyen 2. Így a negyedik körben az algoritmus akármelyik ügynökhöz is rendeli az utolsó tárgyat, nem fog plusz hasznot hozni neki. Tegyük fel, hogy az els® ügynökhöz rendeli.
w
Megjegyezzük, hogy az így megadott Az
ALG
haszonfüggvény monoton szubmoduláris.
által elért összhaszon 3, míg az optimum 4, így az
közelít® semmilyen
w
ALG
nem lehet
δ > 0-ra.
0
A
B
C
D
AB
AC
AD
BC
BD
CD
1
1
1
1
1
2
2
2
1
2
3.2. táblázat. A 3 és 4 elem¶ halmazok haszna legyen 2.
Az
ALG
által adott hozzárendelések és összhasznaik körr®l-körre:
ALG ¨ Osszhaszon
1. kör
2. kör
3. kör
4. kör
1
2
3
3
u1
A
A
AC
ACD
B
B
B
u2 Egy optimális megoldás:
31
(3/4 + δ)-
OP T ¨ Osszhaszon
1. kör
2. kör
3. kör
4. kör
1
2
3
4
u1
A
A
A
AD
B
BC
BC
u2
3.2.16. Állítás. Azonos haszonfüggvény¶ online monoton szubmoduláris árverési feladatokban δ > 0 esetén nem létezik minden alkalmazkodó online ellenfelet (6/7 + δ)-közelít® online algoritmus.
Bizonyítás.
Tegyük fel indirekt, hogy valamely
mazkodó o ine ellenfelet
(6/7 + δ)-közelít®, ALG
δ > 0
esetén létezik egy minden alkal-
nev¶ online algoritmus.
A bizonyítás menete hasonló az el®z® állításéhoz, annyiban van hátrányban az alkalmazkodó online ellenfél az alkalmazkodó o ine-nal szemben, hogy a harmadik tárgy érkezésekor nem tudhatja, hogy az
ALG
melyik ügynökhöz is rendeli az új tárgyat. Ekkor azt
teheti az ellenfél, hogy ® ahhoz az ügynökhöz rendeli a harmadik tárgyat, amelyikhez az
ALG
legfennebb
1/2
Amennyiben az
eséllyel rendelte.
ALG
és az ellenfél ugyanahhoz az ügynökhöz rendelte a harmadik
tárgyat, úgy a negyedik tárgy már semmilyen esetben ne hozzon hasznot. Ekkor úgy az
ALG,
mint az ellenfél összhaszna 3 lesz.
Amennyiben az
ALG és az ellenfél különböz® ügynökökhöz rendelte a harmadik tárgyat,
a negyedik lépésben az ellenfél tegyen úgy, mint az el®z® állítás bizonyításában. Ekkor az
ALG
összhaszna 3, míg az ellenfélé 4.
Így, ha az ellenfelet
ALG
nem lehet
S -nek
nevezzük,
(6/7 + δ)-közelít®
E[cALG (S)] = 3, E[cS (ALG)] ≥ (3 + 4)/2,
semmilyen
így az
δ > 0-ra
3.3. Független azonos eloszlású sztochasztikus bemenettel 3.3.1. De níció. (Független azonos eloszlású sztochasztikus árverési feladat) Legyen M az árverezend® tárgyak típusainak halmaza.Tegyük fel, hogy az árverésen K tárgy egy M
feletti (ismert, vagy ismeretlen) D eloszlás szerint érkezik, egyenként. Legyen az ügynökök halmaza N . Feladatunk a D eloszlásból egyenként és függetlenül érkez® tárgyak visszavonhatatlan társítása egy ügynökhöz. Ekkor a független azonos eloszlású sztochasztikus árverési feladatot egy A(M, D, K, N ) négyesként írhatjuk le, ahol célunk az ügynökök összhasznának maximalizálása.
32
A továbbiakban jelöljük a típusok számát ügynök haszonfüggvényét pedig
m-mel,
az ügynökök számát
n-nel,
az
i.
wi -vel.
Az árverés el®rehaladtával el®fordulhat az, hogy egy ügynöknek egy adott típusú tárgyból több is birtokába kerül. Így az általa birtokolt tárgyak
tihalmazáról
halmaza
helyett a tárgyak
mul-
beszélhetünk, ugyanis a multihalmazokban egy elem többször is el®fordulhat.
Ezért szükségünk van a szubmodularitás multihalmazokra való kiterjesztésére. Egy lehetséges, az árverési feladatok szempontjából észszer¶ megoldást (a csökken® hasznú függvények fogalmát) a következ®kben de niálunk.
3.3.2. Megjegyzés.
Legyen
mi az M
álló multihalmazok között egy
g(x)
azzal az
S
g
típushalmaz i. eleme. Ekkor
N|M | és az M
bijekciót létesíthetünk úgy, hogy minden
multihalmazzal egyenl®, melyben az
mi
típusú elemb®l
x∈
xi
elemeib®l
N|M | esetén
darab van. Így
habár a következ® de níció vektorokkal van megadva, egyértelm¶en átírható multihalmazos alakra.
3.3.3. De níció. (Diszkrét derivált multihalmazok esetén) Egy
f : Nm → R függ-
vény és x ≤ y , x, y ∈ Nm esetén legyen ∆f (y|x) := f (x + y) − f (x) az f -nek x-ben vett y irányú diszkrét deriváltja.
3.3.4. Megjegyzés.
Így a fenti de níció formálisan hasonló a 1.1.1 de nícióhoz, azzal az
értelmi kölönbséggel, hogy multihalmazok esetén az azonos típusú elemek számosságát is gyelembe kell venni.
3.3.5. De níció. (Csökken® hasznú függvények) Egy f
: Nm → R függvény csökken®
hasznú, ha minden x ≤ y , x, y ∈ Nm és minden ei , i ∈ Nm i. egységvektor esetén ∆f (ei |x) ≥ ∆f (ei |x).
3.3.6. Megjegyzés.
Egy
f
csökken® hasznú függvényre az angol szakirodalomban azt
mondják, hogy "f has the property of diminishing returns".
3.3.7. Megjegyzés.
Egy
f : Nm → R
Egy
f : {0, 1}m → R
csökken® hasznú függvény esetén
f {0,1}m
szubmo-
duláris.
3.3.8. Megjegyzés. f0
:
Nm
→ R
szubmoduláris függvény kiterjeszthet® egy
függvénnyé, például a következ® módon:
f 0 (x) := f (min(x, 1)),
ahol a
minimumot koordinátánként vesszük.
3.3.9. De níció. (Monotonitás) Egy f
: Nm → R függvény monoton, ha f (x) ≤ f (y),
minden x ≤ y esetén. 33
3.3.10. Megjegyzés.
Egy
f : Nm → R
függvény pontosan akkor monoton, ha diszkrét
deriváltjai nemnegatívak.
3.3.11. De níció. (Mohó algoritmus) Egy
A(M, D, K, N ) feladatban hívjuk a követ-
kez® algoritmust mohónak. A j tárgy érkezése el®tt legyen az i. ügynökhöz rendelt tárgyak halmaza Ti , az ügynök haszonfüggvénye wi (minden i ∈ 1, . . . N esetén). A j tárgyat érkezésekor ahhoz az ügynökhöz rendeljük, mely haszonfüggvénye maximalizálja a ∆wi (j|Ti ) értéket.
3.3.12. Megjegyzés.
A mohó algoritmusnak nincs szüksége
D
és
K
ismeretére.
A továbbiakban a mohó algoritmus teljesítményét vizsgáljuk.
3.3.13. Lemma. [7] Egy
A(M, D, K, N ) feladat várható optimuma, ahol a j elemhez a
pj valószín¶ség tartozik, S végigfut az összes legfennebb t elem¶ multihalmazon, cj (S) ≥ 0
pedig a j típusú elemek száma S -ben, felülr®l korlátozott az
LP
= max
X
xi,S wi (S) :
i,S
∀j :
X
∀i :
X
xi,S cj (S) ≤ pj t;
i,S
xi,S = 1
S
∀i, S : xi,S ≥ 0
kifejezéssel.
Bizonyítás. t.
Tegyük fel, hogy az árverés során érkezett tárgyak multihalmaza
Vegyük a feladat optimális (o ine) megoldását, ennek összhasznát jelöljük
vel. Legyen
xi,S
annak a valószín¶sége, hogy az optimális megoldásban az
rendelt multihalmaz az
X
xi,S wi (S).
A
j
S.
Ekkor az optimális összhaszon várhatóértéke
típusú elemb®l minden
S
multihalmaz
cj (S)
i.
T , |T | = OP T (T )-
ügynökhöz
E[OP T (T )] =
darabot tartalmaz, így a
i,S hozzárendelt
j
típusú elemek várható száma
X
xi,S cj (S).
Ez az érték nem lehet több,
i,S mint a
T -ben
lev®
j
típusú elemek várható száma, ami
E[cj (M )] = pj t.
Így az
valóban a feladat egy megengedett optimális megoldását határozzák meg. Egy optimális megoldás összhasznának értékét jelöljük
34
xi,S
értékek
OP T := E[OP T (M )]-mel.
3.3.14. Lemma. [7] Tegyük fel, hogy a wi haszonfüggvények monotonok és csökken® hasznúak. Az árverés egy adott pontján legyen Ti az i ügynökhöz rendelt tárgyak pillanatnyi halmaza (i ∈ {1, . . . n}). Ekkor a következ®nek érkez® tárgy hozzárendeléséb®l származó X várható haszon legalább 1t (LP − wi (Ti )). i
Bizonyítás. és legyen
xi,S
Legyen az
yij =
X
értékekb®l alkotott vektor egy megengedett
xi,S cj (S),
ahol
cj (S)
S -ben
az
tárolt
j
LP
megoldás,
típusú elemek száma. Az
LP -
S megszorítások miatt
X
yij ≤ pj t.
Használjuk a
Ti + S
jelölést két multihalmaz uniójára.
i Ekkor a csökken®hasznúság miatt
∆wi (S|Ti ) ≤
X
cj (S)∆wi (j|Ti ).
j A fenti alakú egyenl®tlenségeket
xi,S ≥ 0-val
megszorozva, majd
i
és
S
szerint össze-
gezve kapjuk:
X
xi,S ∆wi (S|Ti ) ≤
i,S
X
xi,S cj (S)∆wi (j|Ti ) =
X
yij ∆wi (j|Ti ).
i,j
i,j,S
∆wi (j|Ti ) ≥ 0 , de níció szerint ∆wi (S|Ti ) = wi (Ti + S) − X miatt pedig xi,S = 1, az el®bbi egyenl®tenségb®l kapjuk:
Mivel a monotonitás miatt
wi (Ti ),
az
LP -megkötések
S
X
xi,S wi (S) −
X
wi (Ti ) ≤
i
i,S
X
yij ∆wi (j|Ti ).
(3.1)
i,j
Most tekintsünk egy, a törtmegoldásokra vonatkozó hipotetikus hozzárendelési szabályt: ha
j
típusú elem érkezik, az
megkötések miatt egy adott elem
pj
nökhöz
j -re
i.
ügynökhöz
yij pj t valószín¶séggel rendeljük (az
e valószín¶ségek összege legfennebb
1).
Mivel
j
valószín¶séggel érkezik egy adott pillanatban, végs®soron egy körben az
j
LP -
típusú
i.
ügy-
yij típusú elemet t valószín¶séggel rendelünk. Így ezen véletlen hozzárendelési
szabállyal
E[véletlen
haszon]
=
X yij i,j
t
∆wi (j|Ti ).
Ekkor (3.1) és (3.2) alapján
E[véletlen
1 haszon] ≥ t
X i,S
35
xi,S wi (S) −
X i
wi (Ti ) .
(3.2)
Vegyük gyelembe, hogy a mohó algoritmus egy olyan ügynökhöz rendeli az éppen érkez® tárgyat, amelyiknek maximális haszna származik ebb®l. Így bármely
xi,S
megen-
gedett megoldás esetén a mohó algoritmus legalább akkora hasznot hoz, mint a véletlen hozzárendelési szabály, ezért az el®bbiekb®l:
E[mohó
haszon]
≥ max E[véletlen
X 1 haszon] ≥ LP − wi (Ti ) . t i
3.3.15. Tétel. [7] A mohó algoritmus (1 − 1/e)-közelít® a független azonos eloszlású sztochasztikus árverési feladatban, amennyiben az ügynökök haszonfüggvényei monotonok és csökken® hasznúak.
Bizonyítás.
Jelölje az els®
τ
elem érkezése utáni hozzárendeléseket
(τ )
(τ )
T1 , . . . , Tn
. Ekkor a
3.3.13 és 3.3.14 lemma alapján a következ®nek érkez® tárgy hozzárendelése utáni összhaszon várhatóértéke
E
X
(τ +1) (τ ) T1 , . . . , Tn(τ ) wi Ti
≥
i A
(τ )
(τ )
X
Vezessük be a
(τ +1) wi Ti
≥E
X
i
(τ ) wi Ti
i
W (τ ) = E
P
i wi
W (τ + 1) ≥ W (τ ) + 1t (LP − W (τ )), − W (τ ))
X 1 (τ ) LP − wi Ti . + t
hozzárendelés szerint várhatóértéket véve a következ®t kapjuk:
i
1 t )(LP
(τ ) wi Ti
i
(T1 , . . . , Tn ) E
X
X 1 (τ ) + E LP − wi Ti . t i
(τ )
Ti
jelölést. Ekkor a legutóbbi egyenl®tlenség
vagy ezzel ekvivalensen
LP − W (τ + 1) ≤ (1 −
alakba írható. Indukcióval kapjuk:
1 τ LP − W (t) ≤ 1 − (LP − W (0)) ≤ e−τ /t LP t A mohó algoritmus által adott hozzárendelés várható összhaszna
W (t) = E
P
t
tárgy érkezése után
(t) i wi (Ti ) . Az eredményeket összesítve kapjuk, hogy
W (t) ≥ (1 − 1/e)LP ≥ (1 − 1/e)OP T.
3.3.16. Tétel. [7] Ha N P
6= RP , adott δ > 0 és fedés-kiértékel® haszonfüggvények esetén
nem létezik olyan polinomiális futásidej¶ online algoritmus, mely (1−1/e+δ)-közelít® lenne független azonos eloszlású bemenettel az online szubmoduláris árverési feladatban. 36
3.3.17. Következmény.
Ha
N P 6= RP ,
adott
δ>0
és csökken® hasznú haszonfüggvé-
nyek esetén nem létezik olyan polinomiális futásidej¶ online algoritmus, mely
(1 − 1/e + δ)-
közelít® lenne független azonos eloszlású bemenettel az online szubmoduláris árverési feladatban.
3.3.18. Megjegyzés.
Az eredményeket összegezve: 3.3.15 tétel, a 3.3.17 következmény és
az ellenfelek típusainak er®sorrendje értelmében monoton csökken® hasznú haszonfüggvények esetén az árverési feladatra létezik mus (pl. a mohó), és semmilyen véletlen online algoritmus, mely
(1 − 1/e)-közelít®
δ > 0
determinisztikus online algorit-
esetén nem létezik olyan polinomiális futásidej¶
(1 − 1/e + δ)-közelít® lenne minden feledékeny, minden al-
kalmazkodó online, illetve minden alkalmazkodó o ine ellenfélhez, hacsak
NP
nem egyenl®
RP -vel. Most nézzük az el®z® feladat egy átfogalmazását:
3.3.19. De níció. (Árverési feladat eloszlásból érkez® független eloszlások esetén) Legyen M az árverezend® tárgyak típusainak halmaza. Legyenek d1 , . . . , dq M feletti eloszlások, D pedig egy {d1 , . . . , dq } feletti eloszlás. Tegyük fel, hogy az árverésen K tárgy egy-egy D-b®l érkez® eloszlás szerint érkezik, egyenként. Legyen az ügynökök halmaza N . Feladatunk a D eloszlásból egyenként és függetlenül érkez® tárgyak visszavonhatatlan társítása egy ügynökhöz. Ekkor az eloszlásból érkez® független eloszlások esetén vett árverési feladatot egy A(M, D, K, N ) négyesként írhatjuk le, ahol célunk az ügynökök összhasznának maximalizálása.
3.3.20. Állítás. A most de niált feladatra ugyanazok az állítások érvényesek, mint a 3.3.1re, bizonyításaik lényegükben ugyanazok. 3.3.1.
Azonos tárgyak esetén
3.3.21. Állítás. A független azonos eloszlású sztochasztikus árverési feladatot, amennyiben azonos tárgyak érkeznek, a mohó algoritmus optimálisan megoldja.
Bizonyítás.
Nyilvánvaló, hogy azonos tárgyak esetén a feladat lényegében elveszíti a szto-
chasztikus jellegét, az egyetlen véletlen változó a kiválasztandó tárgyak száma. Így ugyanazt a feladatot kapjuk eredményül, mint amit a 3.2.1 részben tárgyaltunk. Ezért a 3.2.11 tétel alapján a mohó algoritmus optimális.
37
3.4. Összefoglalás A 3.2 és 3.3 alfejezetekben bemutatott eredmények alapján összeállíthatjuk a következ®, az online szubmoduláris árverési feladat típusaira adható jelenleg ismert legjobb közelítéseket bemutató táblázatot. Mivel minden esetben a mohó az (ismert) legjobb algoritmus, ezért a táblázatban azt tüntettük fel, hogy a különböz® esetekben mekkora a mohó algoritmus közelítési hányadosa, illetve hogy ismert-e, hogy (bizonyos feltevések mellett) nem létezik nála magasabb közelítési hányadost elér® algoritmus. Amennyiben tudjuk, ezt az éles szóval jelöljük, különben egy kérd®jellel. Amelyik esetben a mohó közelítési hányadosa nem ismert, ott az a legsz¶kebb intervallum szerepel, melyben mostani ismeretünk szerint nem tudjuk behatárolni az értékét. A táblázatban szerepl® eredmények mellett szerepel, hogy honnan származnak. Az alapfeladat az online szubmoduláris árverést jelenti monoton szubmoduláris (a sztochasztikus esetben pedig csökken® hasznú) függvények esetén. A táblázatban nem szerepl® részeredmény az, hogy az azonos haszonfüggvények esetében nem létezik alkalmazkodó online ellenfelet
6/7-nél
jobban közelít® online algoritmus.
Sztochasztikus Alapfeladat
1 − 1/e [7];
éles, ha
N P 6= RP [7] 1 [9];
Azonos tárgyak Azonos haszonfv.
Feledékeny
1/2 [8];
Alk. online éles, ha
Alk. o ine
N P 6= RP [7]
éles
[1 − 1/e, 1],?
[1/2, 3/4],?
3.3. táblázat. A mohó algoritmus közelítési hányadosai és élessége az online monoton szubmoduláris árverési feladatban és sajátos eseteiben, a különböz® típusú ellenfelek, ill. a sztochasztikus bemenet esetén.
38
Irodalomjegyzék [1] A.
Krause,
D.
Golovin,
Submodular Function Maximization,
2012,
1-8,
http://las.ethz.ch/ les/krause12survey.pdf [2] S. Albers,
Online Algorithms: a Survey,
2003, 1-6, http://www.cc.gatech.edu/ mi-
hail/D.7520reading/7520onlinesurvey.pdf [3] S. son,
Ben-David,
On
the
A.
Borodin,
Power
of
R.
M.
Karp,
Randomiation
in
Tardos
Online
G.,
A.
Algorithms,
Wisger1994,
http://www.cs.technion.ac.il/ shai/BDBKTW.pdf [4] D.D. Sleator, R. E. Tarjan
Amortized E ciency of List Update and Paging Rules,
1985, http://www.cs.cmu.edu/ sleator/papers/amortized-e ciency.pdf [5] Bélády L. A.,
A Study of Replacement Algorithms for Virtual Storage Computers, 1966
[6] R. M. Karp, U. V. Vazirani, V. V. Vazirani
An Optimal Algorithm for On-line Bipartile
Matching, 1990, http://www.cs.berkeley.edu/ vazirani/pubs/online.pdf [7] M. Karpalov, I. Post, J. Vondrák,
Online Submodular Welfare Maximization: Greedy
is Optimal, 2013, http://theory.stanford.edu/ jvondrak/data/online-alloc.pdf [8] B. Lehmann, D. Lehmann, N. Nisan ,
Combinatorial Suctions with Decreasing Mar-
ginal Utilities, 2006, http://www.cs.huji.ac.il/ noam/submodular.pdf [9] Magánértekezés Long Tran-Thanh-nal
39
