Valószínűségi kerekítés

A számítástechnikában és az operációkutatásban számos kombinatorikus optimalizálási probléma számításilag megoldhatatlan a probléma pontos megoldásához (azaz az optimális megoldás eléréséhez). Sok ilyen probléma gyors ( polinomiális idejű ) közelítő algoritmusokat tesz lehetővé – vagyis olyan algoritmusokat, amelyek garantáltan közel optimális megoldást adnak vissza bármilyen bemenetre.

A valószínűségi kerekítés [1] egy széles körben használt megközelítés ilyen közelítő algoritmusok kidolgozására és elemzésére [2] [3] . Az alapötlet egy valószínűségi módszer alkalmazása egy lineáris programozási (LP) probléma megfelelő optimális megoldásának az eredeti probléma optimális megoldásának közelítésévé való átalakítására.

Áttekintés

Az alapvető megközelítés három lépésből áll:

A problémát egészszámú lineáris programozási (ILP) feladatként fogalmazzuk meg .
Kiszámoljuk a lineáris programozási feladat optimális tört megoldását (egész feltétel nélkül). $x$
A lineáris programozási feladat tört megoldását kerekítjük az egész LP feladat megoldására. $x$ $x'$

(Bár a megközelítés főként lineáris programozást alkalmaz, a feltételek másfajta relaxációja is használható. Például Goeman és Williamson algoritmusa a félig határozott programozási közelítő maximum vágási algoritmust használja .)

Az első lépés célja az egész lineáris programozási feladat megfelelő utasításának kiválasztása. Ez megköveteli a lineáris programozás alapos ismeretét, és különösen annak megértését, hogyan lehet a problémákat lineáris programozással és egész lineáris programozással modellezni. Azonban sok probléma esetén létezik egy jól teljesítő természetes egész lineáris programozási probléma, amint az a probléma lefedő példájában látható. (Egy egészszámú lineáris programozási feladatnak kis integer résnek kell lennie. Ezenkívül a valószínűségi kerekítést gyakran használják az egész számok közötti eltérések bizonyítására.)

A második lépésben az optimális tört megoldás általában polinomiális időben számítható ki egy szabványos lineáris programozási algoritmus segítségével .

A harmadik lépésben a tört megoldást egész megoldássá (és ezáltal az eredeti feladat megoldásává) kell átalakítani. Ezt a folyamatot frakcionált megoldás kerekítésnek nevezzük . A végső egész megoldásnak (bizonyíthatóan) olyan árral kell rendelkeznie, amely nem sokban tér el a tört megoldás árától. Ez biztosítja, hogy egy egész számú megoldás költsége ne legyen sokkal nagyobb, mint egy optimális egész megoldás költsége.

A harmadik lépésben (kerekítés) alkalmazott fő technika a valószínűségi megközelítés alkalmazása, majd a valószínűségi érvelés a kerekítéssel járó áremelkedés korlátozása érdekében. Itt valószínűségi argumentumokat használunk a kívánt tulajdonságokkal rendelkező diszkrét struktúra létezésének kimutatására. Ebben az összefüggésben a valószínűségi argumentumokat a következők bemutatására használjuk:

Adott néhány tört megoldás az LP feladatra, a valószínűségi kerekítés pozitív valószínűséggel olyan egész megoldást

x

x'

x

ad , amely valamilyen kívánt kritérium szerint közelít .

Végül, hogy a harmadik lépés számításilag hatékony legyen, vagy nagy valószínűséggel közelinek mutatjuk be (hogy a lépés valószínűségi maradjon), vagy a kerekítési lépést derandomizáljuk , általában feltételes valószínűségekkel . Ez utóbbi módszer a valószínűségi kerekítési folyamatot egy hatékony determinisztikus folyamattá alakítja át, amely garantáltan jó eredményt ad. $x'$ $x$

Összehasonlítás a valószínűségi módszer más alkalmazásaival

A valószínűségi kerekítési lépés két szempontból különbözik a valószínűségi módszer legtöbb alkalmazásától:

A kerekítési lépés számítási összetettsége fontos. A lépést gyors algoritmussal (azaz polinomiális idő algoritmussal ) kell megvalósítani.
A véletlenszerű kísérlet alapjául szolgáló valószínűségi eloszlás egy lineáris programozási probléma egy példányának megoldásának függvénye. Ez a tény meghatározó a közelítő algoritmus garantált hatékonyságának bizonyítása szempontjából. Ez azt jelenti, hogy a probléma bármely példányára az algoritmus olyan megoldást ad vissza, amely megközelíti az adott példány optimális megoldását . Összehasonlításképpen, a valószínűségi módszer alkalmazásai a kombinatorikában általában olyan struktúrák létezését mutatják, amelyek tulajdonságai a bemeneti paraméterektől függenek. Vegyük például a Turan-tételt , amely kijelenthető: "minden csúcsokkal és középfokkal rendelkező gráfnak rendelkeznie kell egy független mérethalmazzal ." (Lásd a " Feltételes valószínűségek módszere " cikket a Turán-tétel valószínűségi bizonyításához.) Bár vannak gráfok, amelyeknél ez a korlát pontos, vannak olyan gráfok is, amelyek független halmazai sokkal nagyobbak, mint . Így egy gráfban létező független halmaz mérete a Turán-tétel szerint általában sokkal kisebb lehet, mint a gráf maximális független halmaza. $x$ $n$ $d$ $n/(d+1)$ $n/(d+1)$

Példa egy beállított borítóra

A módszert egy példával lehet a legjobban illusztrálni. A következő példa bemutatja, hogyan lehet véletlenszerű kerekítéssel egy közelítő algoritmust létrehozni a beállított fedőprobléma számára .

Vegyük a halmazlefedési probléma bármely példányát a gyűjteményben . $\langle c,{\mathcal {S}}\rangle$ ${\mathcal {U}}$

Az 1. lépésben legyen az egész szám LP probléma a szabványos egész lineáris programozási probléma a halmaz lefedésére .

A 2. lépésben legyen az LP probléma az ILP probléma gyengítése az LP problémára, és legyen ennek a gyengített problémának az optimális megoldása, amelyet bármely szabványos lineáris programozási algoritmus kaphat . (Az LP probléma megoldásához szükséges idő polinomiálisan függ a bemenet méretétől.) $x^{*}$

(Az LP probléma érvényes megoldásai olyan vektorok , amelyek minden halmazhoz nemnegatív súlyt rendelnek , úgy, hogy bármely elemhez , fedek - a , -t tartalmazó halmazokhoz rendelt összsúly legalább 1, azaz $x$ $s\in {\mathcal {S))$ $x_{s}$ $e\in {\mathcal {U}}$ $x'$ $e$ $e$

\sum _{s\ni e}x_{s}\geq 1.

Az optimális megoldás egy megvalósítható megoldás, amelynek költsége $x^{*}$

\sum _{s\in {\mathcal {U}}}c(S)x_{s}^{*}

a lehető legkisebb.)

Ne feledje, hogy a készlet bármely borítója megvalósítható megoldást ad ( ahol a -ra , ellenkező esetben). Ennek a fedezetnek az ára megegyezik az árral , azaz ${\mathcal C}$ ${\mathcal {S))$ $x$ $x_{s}=1$ $s\in {\mathcal {C))$ $x_{s}=0$ ${\mathcal C}$ $x$

\sum _{s\in {\mathcal {C}}}c(s)=\sum _{s\in {\mathcal {S}}}c(s)x_{s}.

Más szóval, a lineáris programozási probléma az adott halmazlefedési probléma relaxációja.

Mivel az LP-probléma megvalósítható megoldásai közül ennek van a minimális ára, ezért az ár a halmaz optimális fedezetének költségének alsó korlátja . $x^{*}$ $x^{*}$

3. lépés: Véletlenszerű kerekítés

Az alábbiakban ismertetjük a harmadik lépés leírását, a kerekítési lépést, amelynek a minimális árkészlet részleges fedezetét kell érvényes egész megoldássá konvertálnia (a megfelelő halmazfedezetnek megfelelően). $x^{*}$ $x'$

A kerekítési lépés olyan megoldást ad , amely pozitív valószínűséggel az ártól kis mértékben eltér ára. Ekkor (mivel az ár az optimális lefedettség árának alsó határa), az ár kis mértékben el fog térni az optimális ártól. $x'$ $x^{*}$ $x^{*}$ $x'$

Kiindulásként vegye figyelembe a legtermészetesebb kerekítési sémát:

Minden egyes halmaz esetében valószínűséggel veszünk , ellenkező esetben .

s\in {\mathcal {S))

x'_{s}=1

\min(1,x_{s}^{*})

x'_{s}=0

E kerekítési séma szerint a kiválasztott készletek árának matematikai elvárása nem haladja meg a részfedezet árát. Ez jó, de sajnos a lefedettség nem jó. Ha a változók kicsik, annak a valószínűsége, hogy az elemet nem fedi le, hozzávetőleges $\sum _{s}c(s)x_{s}^{*}$ $x_{s}^{*}$ $e$

\prod _{s\ni e}1-x_{s}^{*}\approx \prod _{s\ni e}\exp(-x_{s}^{*})=\exp { \Big (}-\sum _{s\ni e}x_{s}^{*}{\Big )}\approx \exp(-1).

Így a lefedett elemek arányának matematikai elvárása állandó lesz.

Annak érdekében , hogy nagy valószínűséggel lefedje az összes elemet, a standard kerekítési séma először egy megfelelő tényezővel növeli a kerekítési valószínűségeket . Szabványos kerekítési séma: $x'$ $\lambda >1$

Javítjuk a paramétert . Minden készlethez ,

\lambda \geq 1

s\in {\mathcal {S))

valószínűséggel veszünk , ellenkező esetben .

x'_{s}=1

\min(\lambda x_{s}^{*},1)

x'_{s}=0

A valószínűségek szorzata -val növeli az ár várható értékét , de valószínűbbé teszi az összes elem lefedettségét. Itt az az ötlet, hogy a lehető legkisebbre válasszunk, hogy minden elem bizonyíthatóan nem nulla valószínűséggel lefedve legyen. Az alábbiakban egy részletes elemzés található. $\lambda$ $\lambda$ $\lambda$

Lemma (a kerekítési séma garantált hatékonysága) Javítjuk . Pozitív valószínűséggel a kerekítési séma olyan fedezetet ad vissza , amelynek költsége nem haladja meg (és ez a költség az optimális beállított fedezet költségének szorzójával tér el ).

\lambda =\ln(2|{\mathcal {U}}|)

x'

2\ln(2|{\mathcal {U}}|)c\cdot x^{*}

O(\log |{\mathcal {U}}|)

(Ne feledje, hogy némi körültekintéssel az értéket le lehet csökkenteni .) $O(\log |{\mathcal {U}}|)$ $\ln(|{\mathcal {U}}|)+O(\log \log |{\mathcal {U}}|)$

Bizonyítás

A véletlenszerű kerekítési séma kimenete a kívánt tulajdonságokkal rendelkezik mindaddig, amíg a következő "rossz" események bekövetkeznek: $x'$

a megoldás ára meg fogja haladni $c\cdot x'$ $x'$ $2\lambda c\cdot x^{*}$
egyes elemeknél nem terjed ki . $e$ $x'$ $e$

Mindegyik matematikai elvárása nem haladja meg a . A matematikai elvárás linearitása miatt az elvárás nem haladja meg a . Ekkor a Markov-egyenlőtlenség szerint az első rossz esemény valószínűsége nem haladja meg a . ${\displaystyle x'_{s))$ $\lambda x_{s}^{*}$ $c\cdot x'$ $\sum _{s}c(s)\lambda x_{s}^{*}=\lambda c\cdot x^{*}$ $1/2$

A fennmaradó rossz eseményekhez (egy elemhez egyet ) vegye figyelembe, hogy mivel , bármely adott elemére a nem fedezett valószínűség $e$ $\sum _{s\ni e}x_{s}^{*}\geq 1$ $e$ $e$

{\begin{aligned}\prod _{s\ni e}{\big (}1-\min(\lambda x_{s}^{*},1){\big )}&<\prod _{s\ni e}\exp({-}\lambda x_{s}^{*})=\exp {\Big (}{-}\lambda \sum _{s\ni e}x_{s} ^{*}{\Big )}\\&\leq \exp({-}\lambda )=1/(2|{\mathcal {U}}|).\end{igazított}}

(Itt az egyenlőtlenséget használjuk , ami szigorúan igaz -ra .) $1+z\leq e^{z}$ $z\neq 0$

Így tetszőleges számú elem esetén annak a valószínűsége, hogy az elemet nem fedi le, kisebb, mint . $|{\mathcal {U}}|$ $1/(2{\mathcal {U}})$

Kisebb annak a valószínűsége, hogy valamelyik rossz esemény megtörténik . Ekkor a rossz események hiányának valószínűsége nagyobb, mint nulla, és ez a halmaz fedezete, amelynek költsége nem haladja meg a . $1+|{\mathcal {U}}|$ $1/2+|{\mathcal {U}}|/(2{\mathcal {U}})=1$ $x'$ $2\lambda c\cdot x^{*}$

QED (amit be kellett bizonyítani)

Derandomizálás a feltételes valószínűségek módszerével

A fenti lemma azt mutatja , hogy létezik egy készlet borítója, amelynek költsége ). Ebben az összefüggésben a célunk egy hatékony közelítő algoritmus, nem csak a létezés bizonyítása, ezért még nem fejeztük be a 3. lépést. $O(\log(|{\mathcal {U}}|)c\cdot x^{*}$

Egyik megközelítésként lehetne egy kicsit növelni , majd megmutatni, hogy a siker valószínűsége legalább 1/4. Ezzel a módosítással, a véletlenszerű kerekítési lépés többszöri megismétlésével nagy valószínűséggel biztosítható a siker. $\lambda$

Ez a megközelítés gyengíti a garantált hatékonyságot, de leírunk egy másik megközelítést, amely egy olyan determinisztikus algoritmust eredményez, amely biztosítja a fent jelzett garantált hatékonyságot. A megközelítést feltételes valószínűségek módszerének nevezik .

A determinisztikus algoritmus egy valószínűségi kerekítési sémát emulál – minden halmazt figyelembe vesz , és azonban ahelyett, hogy véletlenszerűen választana a alapján , az algoritmus determinisztikus választást hoz, így a választás által meghatározott feltételes meghibásodási valószínűség 1-nél kisebb marad . $s\in {\mathcal {S))$ $x'_{s}\in \{0,1\}$ $x^{*}$

A meghibásodás feltételes valószínűségének megkötése

Minden változó értékét úgy szeretnénk beállítani , hogy a feltételes meghibásodási valószínűség 1-nél kisebb legyen. Ennek eléréséhez jó korlátra van szükségünk a feltételes meghibásodási valószínűségre vonatkozóan. A határt az eredeti létezési bizonyíték újralátogatásával kapjuk meg. Ez a bizonyítás implicit módon a valószínűségi változó várható értékére korlátozza a sikertelenség valószínűségét ${\displaystyle x'_{s))$

F={\frac {c\cdot x'}{2\lambda c\cdot x^{*}}}+|{\mathcal {U}}^{(m)}|

ahol

{\mathcal {U}}^{(m)}={\Big \{}e:\prod _{s\ni e}(1-x'_{s})=1{\Big \ }}

a fedetlenül hagyott elemek halmaza.

A valószínűségi változó kissé rejtélyesnek tűnhet, de a valószínűségi bizonyítás szisztematikus megközelítését tükrözi. A képlet első tagját úgy kapjuk meg, hogy a Markov-egyenlőtlenségeket alkalmazzuk az első rossz eseményhez kötött valószínűségre (a költség túl magas). Ez a tag legalább 1-gyel járul hozzá, ha az ár túl magas. A második tag a második típusú rossz események (fedetlen elemek) számát számolja. Legalább 1-gyel járul hozzá, ha bármilyen elemet fedetlenül hagy. Így minden 1-nél kisebb kimenetnél a megoldásnak minden elemet le kell fednie, és a lemma kívánt korlátjának megfelelő árral kell rendelkeznie. Röviden, ha a kerekítési lépés sikertelen, . Ebből következik ( Markov egyenlőtlensége szerint ), hogy mi a kudarc valószínűségének felső korlátja. Vegye figyelembe, hogy a fenti érvek implicit módon már jelen vannak a lemma bizonyításában, ami azt is mutatja, hogy . $F$ $F$ $F$ $x'$ $F$ $x'$ $F$ $x'$ $F\geq 1$ $E[F]$ $E[F]<1$

A feltételes valószínűségi módszer alkalmazásához ki kell terjesztenünk a feltételes meghibásodási valószínűség korlátozásának indoklását a kerekítési lépés során. Ez általában szisztematikusan megtehető, bár technikailag időigényes lehet.

Tehát mekkora a sikertelenség feltételes valószínűsége, ha a kerekítési lépés végighalad a halmazokon? Mivel minden eredmény azt jelenti, hogy a kerekítési lépés kudarchoz vezetett, a Markov-féle egyenlőtlenség szerint a sikertelenség feltételes valószínűsége nem haladja meg a feltételes várakozást . $F\geq 1$ $F$

Ezután kiszámítjuk a feltételes átlagot , ugyanúgy, mint az eredeti bizonyításban. Tekintsük a kerekítési folyamat állapotát minden iteráció végén . Jelölje a beolvasott halmazokat (az első halmazokat a -ban ). Jelöljön egy (részben hozzárendelt) vektort (csak akkor van így definiálva, ha ). Egy ilyen halmaz esetén jelölje azt a valószínűséget, amellyel 1-hez lesz rendelve. Tartalmazzon fedetlen elemeket. Ekkor a választás által adott feltételes elvárás , azaz a döntés adta , akkor $F$ $F$ $t$ $S^{{(t)}}$ $t$ ${\mathcal {S))$ ${\displaystyle x^{(t)))$ $x'$ ${\displaystyle x_{s}^{(t)))$ ${\displaystyle s\in S^{(t)))$ ${\displaystyle s\not \in S^{(t)))$ $p_{s}=\min(\lambda x_{s}^{*},1)$ ${\displaystyle x'_{s))$ ${\displaystyle {\mathcal {U}}^{(t)))$ $F$ ${\displaystyle x^{(t)))$

E[F|x^{(t)}]~=~{\frac {\sum _{s\in S^{(t)))c(s)x'_{s}+\sum _{s\not \in S^{(t)}}c(s)p_{s}}{2\lambda c\cdot x^{*}}}~+~\sum _{e\in {\ mathcal {U}}^{(t)}}\prod _{s\not \in S^{(t)},s\ni e}(1-p_{s}).

Ne feledje, hogy csak a iteráció után kerül meghatározásra . $E[F|x^{(t)}]$ $t$

A meghibásodás feltételes valószínűségének 1-nél kisebb tartása

Ahhoz, hogy a meghibásodás feltételes valószínűsége 1-nél kisebb legyen, elegendő a feltételes átlagot 1-nél kisebb értéken tartani. Ehhez elegendő elkerülni a feltételes átlag növekedését, és ezt fogja tenni az algoritmus. Az algoritmus minden iterációnál úgy lesz beállítva $F$ $F$ ${\displaystyle x'_{s))$

E[F|x^{(m)}]\leq E[F|x^{(m-1)}]\leq \cdots \leq E[F|x^{(1)}]\ leqE[F|x^{(0)}]<1

(hol ). $m=|{\mathcal {S}}|$

Egy iterációnál hogyan állítható be az algoritmus a következőre ? Kiderült, hogy egyszerűen beállíthatja , hogy utánozza az értékét . $t$ ${\displaystyle x'_{s'))$ $E[F|x^{(t)}]\leq E[F|S^{(t-1)}]$ ${\displaystyle x'_{s'))$ $E[F|x^{(t)}]$

Az ok megértéséhez vegye figyelembe az iteráció kezdetének időpontját. Ezen a ponton az érték meg van határozva, de az érték definiálatlan – két lehetséges értéket vehet fel, attól függően, hogy hogyan van beállítva az iterációban . A Let értéket jelent . Jelölje a két lehetséges értékét , attól függően, hogy 0-ra vagy 1-re van állítva. A feltételes elvárás definíciója szerint, $t$ $E[F|x^{(t-1)}]$ $E[F|x^{(t)}]$ ${\displaystyle x'_{s'))$ $t$ ${\displaystyle E^{(t-1)))$ $E[F|x'^{(t-1)}]$ ${\displaystyle E_{0}^{(t)))$ ${\displaystyle E_{1}^{(t)))$ $E[F|x^{(t)}]$ ${\displaystyle x'_{s'))$

E^{(t-1)}~=~\Pr[x'_{s'}=0]E_{0}^{(t)}+\Pr[x'_{s'}= 1]E_{1}^{(t)}.

Mivel két mennyiség súlyozott átlaga mindig nagyobb vagy egyenlő, mint a legkisebb mennyiség, ebből az következik

E^{(t-1)}~\geq ~\min(E_{0}^{(t)},E_{1}^{(t)}).

Így a kapott érték minimálisra csökkentése biztosítja, hogy . Ezt fogja tenni az algoritmus. ${\displaystyle x'_{s'))$ $E[F|x^{(t)}]$ $E[F|x^{(t)}]\leq E[F|x^{(t-1)}]$

Részletesen, mit jelent ez? A függvény függvényének tekintve (az összes többi rögzített értékkel együtt), ez a függvény lineáris -ben , és az at együttható ebben a függvényben $E[F|x^{(t)}]$ ${\displaystyle x'_{s'))$ ${\displaystyle x'_{s'))$ ${\displaystyle x'_{s'))$

{\frac {c_{s'}}{2\lambda c\cdot x^{*}}}~-~\sum _{e\in s'\cap {\mathcal {U}}_{ t-1}}\prod _{s\not \in S^{(t)},s\ni e}(1-p_{s}).

Így az algoritmusnak 0-ra kell állítania, ha ez a kifejezés pozitív, és 1-re egyébként. Mindez a következő algoritmust adja. ${\displaystyle x'_{s'))$

Valószínűségi kerekítési algoritmus beállított lefedettséghez

bemenet: halmazok halmaza , populáció , árvektor ${\mathcal {S))$ ${\mathcal {U}}$ $c$

kimenet: lefedettség halmaza (egy szabványos egész lineáris programozási probléma megoldása egy halmaz lefedésére) $x'$

Kiszámítjuk a halmaz törtfedezetét minimális költséggel (a megfelelő lineáris programozási feladat optimális megoldása). $x^{*}$
Hozzárendeljük . Bármelyikhez hozzárendeljük . $\lambda \leftarrow \ln(2|{\mathcal {U}}|)$ $p_{s}\leftarrow \min(\lambda x_{s}^{*},1)$ $s\in {\mathcal {S))$
Bármelyikre , amit csinálunk: $s'\in {\mathcal {S))$
1. Hozzárendeljük . ( olyan készleteket tartalmaz, amelyekről még nem született döntés.) ${\mathcal {S}}\leftarrow {\mathcal {S}}-\{s'\}$ ${\mathcal {S))$
2. Ha egy ${\frac {c_{s'}}{2\lambda c\cdot x^{*}}}>\sum _{e\in s'\cap {\mathcal {U}}}\prod _ {s\in {\mathcal {S}},s\ni e}(1-p_{s})$ majd kijelöljük $x'_{s}\leftarrow 0$ ellenkező esetben rendelje hozzá és . $x'_{s}\leftarrow 1$ ${\mathcal {U}}\leftarrow {\mathcal {U}}-s'$ ( még nem tárgyalt elemeket tartalmaz.) ${\mathcal {U}}$
Visszatérünk . $x'$

Lemma (az algoritmus garantált hatékonysága) A fenti algoritmus egy halmazfedezetet ad vissza , amelynek ára nem haladja meg a (töredékes) halmazfedezet minimális árát.

x'

2\ln(2|{\mathcal {U}}|)

Bizonyítás

Az algoritmus biztosítja, hogy a feltételes elvárás ne nőjön minden iterációnál. Mivel ez a feltételes elvárás eredetileg kisebb volt 1-nél (amint fentebb látható), az algoritmus biztosítja, hogy a feltételes elvárás 1-nél kisebb maradjon. Mivel a meghibásodás feltételes valószínűsége nem haladja meg a feltételes elvárást , az algoritmus biztosítja, hogy a meghibásodás feltételes valószínűsége megmaradjon. 1-nél kisebb. Így az algoritmus végén, amikor minden elem definiálva van, az algoritmus sikeres eredményt kap. Ez azt jelenti, hogy a fenti algoritmus egy halmazfedelet ad vissza , amelynek ára nem haladja meg egyetlen (töredékes) halmazfedezet minimális árát. $F=E[F\,|\,x^{(t)}]$ $F$ $x'$ $2\ln(2|{\mathcal {U}}|)$

Megjegyzések az algoritmushoz

A fenti példában az algoritmus egy valószínűségi változó feltételes elvárásán alapult . Egyes esetekben a pontos feltételes elvárás helyett egy bizonyos értékű feltételes elvárás felső (és esetenként alsó) korlátját alkalmazzák. Ezt pesszimista becslésnek nevezzük . $F$

Lásd még

Feltételes valószínűségi módszer

Irodalom

Rajeev Motwani, Prabhakar Raghavan. Véletlenszerű algoritmusok . - Cambridge University Press , 1995. - ISBN 978-0-521-47465-8 .
Vijay Vazirani. Közelítő algoritmusok . - Springer Verlag , 2001. - ISBN 978-3-540-65367-7 .
Prabhakar Raghavan, Clark D. Thompson. Véletlenszerű kerekítés: Egy technika bizonyíthatóan jó algoritmusokhoz és algoritmikus bizonyításhoz // Combinatorica . - 1987. - T. 7 , sz. 4 . – S. 365–374 . - doi : 10.1007/BF02579324 .
Prabhakar Raghavan. Determinisztikus algoritmusok valószínűségi felépítése: egészszámú programok közelítése // Journal of Computer and System Sciences . - 1988. - T. 37 , sz. 2 . – S. 130–143 . - doi : 10.1016/0022-0000(88)90003-7 .

Link

Ingo Althofer. A véletlenszerű stratégiák és konvex kombinációk ritka közelítéseiről // Lineáris algebra és alkalmazásai. - 1994. - T. 199 . – S. 339–355 . - doi : 10.1016/0024-3795(94)90357-3 .
Thomas Lefmann, Hanno Lefmann. Ritka közelítések determinisztikus számítása // Lineáris algebra és alkalmazásai. - 1996. - T. 240 . — P. 9–19 . - doi : 10.1016/0024-3795(94)00175-8 .
Richard J. Lipton, Neal E. Young. Egyszerű stratégiák nagy zéró összegű játékokhoz a komplexitáselmélet alkalmazásával // STOC '94: Proceedings of the huszonhatodik éves ACM szimpózium a számítástechnika elméletéről. - New York, NY: ACM , 1994. - S. 734-740. — ISBN 0-89791-663-8 . - doi : 10.1145/195058.195447 .