Probabilistisk avrundning

Inom datavetenskap och operationsforskning är många kombinatoriska optimeringsproblem beräkningsmässigt svårlösta för att lösa problemet exakt (dvs. för att få den optimala lösningen). Många sådana problem tillåter snabba ( polynom-tid ) approximationsalgoritmer - det vill säga algoritmer som garanterat ger en nästan optimal lösning för alla indata.

Probabilistisk avrundning [1] är ett allmänt använt tillvägagångssätt för att utveckla och analysera sådana approximationsalgoritmer [2] [3] . Grundidén är användningen av en probabilistisk metod för att omvandla den motsvarande optimala lösningen av ett linjärt programmeringsproblem (LP) till en approximation till den optimala lösningen av det ursprungliga problemet.

Översikt

Det grundläggande tillvägagångssättet har tre steg:

Vi formulerar problemet som ett heltalslinjär programmeringsproblem (ILP).
Vi beräknar den optimala fraktionella lösningen av det linjära programmeringsproblemet (utan heltalsvillkoret). $x$
Vi avrundar bråklösningen av det linjära programmeringsproblemet till lösningen av heltals-LP-problemet. $x$ $x'$

(Även om tillvägagångssättet huvudsakligen använder linjär programmering, kan andra typer av relaxation av villkor användas. Till exempel använder Goeman och Williamsons algoritm den semidefinitiva programmeringens ungefärliga maximala cut-algoritm .)

Målet med det första steget är att välja en lämplig beskrivning av heltalslinjärprogrammeringsproblemet. Detta kräver goda kunskaper i linjär programmering, och i synnerhet förståelse för hur man modellerar problem med linjär programmering och heltalslinjär programmering. Men för många problem finns det ett välpresterande naturligt heltalslinjärt programmeringsproblem, som visas i uppsättningen som täcker problemexemplet. (Ett heltals linjärt programmeringsproblem bör ha ett litet heltalsgap. Dessutom används sannolikhetsavrundning ofta för att bevisa heltalsgap.)

I det andra steget kan den optimala fraktionella lösningen vanligtvis beräknas i polynomtid med hjälp av en vanlig linjär programmeringsalgoritm .

I det tredje steget måste bråklösningen omvandlas till en heltalslösning (och därmed till lösningen av det ursprungliga problemet). Denna process kallas fraktionell lösningsavrundning . Den slutliga heltalslösningen måste (bevisligen) ha ett pris som inte skiljer sig mycket från priset på bråklösningen. Detta säkerställer att kostnaden för en heltalslösning inte är mycket större än kostnaden för en optimal heltalslösning.

Den huvudsakliga tekniken som används i det tredje steget (avrundning) är att använda ett probabilistiskt tillvägagångssätt och sedan använda sannolikhetsresonemang för att begränsa prisökningen som följer med avrundning. Här används probabilistiska argument för att visa att det finns en diskret struktur med önskade egenskaper. I detta sammanhang används probabilistiska argument för att visa följande:

Givet någon bråkdelslösning på LP-problemet ger probabilistisk avrundning med positiv sannolikhet en heltalslösning som approximerar

x

x'

x

enligt något önskat kriterium.

Slutligen, för att göra det tredje steget beräkningseffektivt, antingen visas det vara nära med hög sannolikhet (så att steget förblir probabilistiskt), eller så avrundas steget avrandomiserat , vanligtvis med villkorade sannolikheter . Den senare metoden omvandlar den probabilistiska avrundningsprocessen till en effektiv deterministisk process som garanterat ger en bra utdata. $x'$ $x$

Jämförelse med andra tillämpningar av den probabilistiska metoden

Det probabilistiska avrundningssteget skiljer sig från de flesta tillämpningar av den probabilistiska metoden i två avseenden:

Den beräkningsmässiga komplexiteten för avrundningssteget är viktig. Steget måste implementeras av en snabb algoritm (dvs en polynomisk tidsalgoritm ).
Sannolikhetsfördelningen bakom ett slumpmässigt experiment är en funktion av lösningen på en instans av ett linjärt programmeringsproblem. Detta faktum är avgörande för beviset på den garanterade effektiviteten hos approximationsalgoritmen. Det vill säga, för alla instanser av problemet, returnerar algoritmen en lösning som approximerar den optimala lösningen för den specifika instansen . Som jämförelse visar tillämpningar av den probabilistiska metoden i kombinatorik vanligtvis förekomsten av strukturer vars egenskaper beror på ingångsparametrarna. Tänk till exempel på Turans teorem , som kan anges som "alla grafer med hörn och medelgrad måste ha en oberoende uppsättning storlek åtminstone ." (Se artikeln " Metod för betingade sannolikheter " för ett probabilistiskt bevis på Turáns sats.) Även om det finns grafer för vilka denna gräns är exakt, finns det också grafer som har oberoende mängder mycket större än . Således kan storleken på en oberoende mängd som finns i en graf enligt Turáns sats i allmänhet vara mycket mindre än den maximala oberoende mängden av grafen. $x$ $n$ $d$ $n/(d+1)$ $n/(d+1)$

Ett exempel på en uppsättningsomslag

Metoden illustreras bäst med ett exempel. Följande exempel visar hur slumpmässig avrundning kan användas för att skapa en approximationsalgoritm för uppsättningstäckningsproblemet .

Ta alla exempel på problem med uppsättningen som täcker insamlingen . $\langle c,{\mathcal {S}}\rangle$ ${\mathcal {U}}$

För steg 1, låt heltals-LP-problemet vara standardheltalslinjärprogrammeringsproblemet för att täcka uppsättningen .

För steg 2, låt LP-problemet vara försvagningen av ILP-problemet till LP-problemet, och låt vara den optimala lösningen på detta försvagade problem som erhålls av vilken linjär standardprogrammeringsalgoritm som helst . (Den tid som krävs för att lösa LP-problemet beror polynomiellt på storleken på inmatningen.) $x^{*}$

(De giltiga lösningarna på LP-problemet är vektorer som tilldelar varje uppsättning en icke-negativ vikt , så att för alla element täcker - den totala vikten som tilldelas uppsättningar som innehåller , är minst 1, dvs. $x$ $s\in {\mathcal {S))$ $x_{s}$ $e\in {\mathcal {U}}$ $x'$ $e$ $e$

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

En optimal lösning är en genomförbar lösning vars kostnad är $x^{*}$

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

så liten som möjligt.)

Observera att varje lock på setet för ger en möjlig lösning (var för , annars). Priset för denna täckning är lika med priset , det vill säga ${\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}.

Med andra ord är det linjära programmeringsproblemet en avslappning av det givna uppsättningstäckningsproblemet.

Eftersom det har minimipriset bland de möjliga lösningarna på LP-problemet, är priset den nedre gränsen för kostnaden för den optimala täckningen av setet . $x^{*}$ $x^{*}$

Steg 3: Slumpmässig avrundning

Nedan följer en beskrivning av den tredje stegsbeskrivningen, avrundningssteget, som ska omvandla den partiella täckningen av minimiprisuppsättningen till en giltig heltalslösning (motsvarande korrekt uppsättningstäckning). $x^{*}$ $x'$

Avrundningssteget kommer att ge en lösning , som med positiv sannolikhet har ett pris som skiljer sig från priset med en liten faktor. Sedan (eftersom priset är den nedre gränsen för priset för den optimala settäckningen), kommer priset att skilja sig från det optimala priset med en liten faktor. $x'$ $x^{*}$ $x^{*}$ $x'$

Som utgångspunkt, överväg det mest naturliga avrundningsschemat:

För varje uppsättning i tur och ordning tar vi med sannolikhet , annars tar vi .

s\in {\mathcal {S))

x'_{s}=1

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

x'_{s}=0

Enligt detta avrundningsschema överstiger inte den matematiska förväntningen på priset för de valda uppsättningarna , priset för partiell täckning. Detta är bra, men tyvärr är täckningen inte bra. Om variablerna är små är sannolikheten att elementet inte täcks ungefär $\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 (}-\summa _{s\ni e}x_{s}^{*}{\Big )}\approx \exp(-1).

Således kommer den matematiska förväntan på andelen täckta element att vara konstant.

För att göra det mycket troligt att det täcker alla delar, höjer standardavrundningsschemat först avrundningssannolikheterna med en lämplig faktor . Standard avrundningsschema: $x'$ $\lambda >1$

Vi fixar parametern . För varje set ,

\lambda \geq 1

s\in {\mathcal {S))

vi tar med sannolikhet , annars tar vi .

x'_{s}=1

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

x'_{s}=0

Att multiplicera sannolikheterna med ökar det förväntade värdet av priset med , men gör täckningen av alla element mer sannolikt. Tanken här är att välja så litet som möjligt så att alla element bevisligen täcks med en sannolikhet som inte är noll. Nedan följer en detaljerad analys. $\lambda$ $\lambda$ $\lambda$

Lemma (garanterad effektivitet av avrundningsschemat) Vi fixar . Med en positiv sannolikhet kommer avrundningsschemat att returnera en täckning med en kostnad som inte överstiger (och denna kostnad skiljer sig med en faktor av kostnaden för den optimala uppsättningstäckningen).

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

x'

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

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

(Observera att värdet med viss försiktighet kan reduceras till .) $O(\log |{\mathcal {U}}|)$ $\ln(|{\mathcal {U}}|)+O(\log \log |{\mathcal {U}}|)$

Bevis

Utdata från det slumpmässiga avrundningsschemat har de önskade egenskaperna tills följande "dåliga" händelser inträffar: $x'$

priset på lösningen kommer att överstiga $c\cdot x'$ $x'$ $2\lambda c\cdot x^{*}$
för vissa element , täcker inte . $e$ $x'$ $e$

De matematiska förväntningarna på var och en överstiger inte . På grund av den matematiska förväntans linjäritet överstiger förväntan inte . Sedan, enligt Markov-ojämlikheten , överstiger inte sannolikheten för den första dåliga händelsen . ${\displaystyle x'_{s))$ $\lambda x_{s}^{*}$ $c\cdot x'$ $\sum _{s}c(s)\lambda x_{s}^{*}=\lambda c\cdot x^{*}$ $1/2$

För de återstående dåliga händelserna (en för varje element av ) notera att eftersom , för en given del av , sannolikheten som inte täcks är $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{aligned}}

(Här använder vi ojämlikheten , vilket är strikt sant för .) $1+z\leq e^{z}$ $z\neq 0$

För ett valfritt antal element är alltså sannolikheten att elementet inte täcks mindre än . $|{\mathcal {U}}|$ $1/(2{\mathcal {U}})$

Sannolikheten att en av de dåliga händelserna inträffar är mindre . Då är sannolikheten för frånvaron av dåliga händelser större än noll och är en täckning av uppsättningen med en kostnad som inte överstiger . $1+|{\mathcal {U}}|$ $1/2+|{\mathcal {U}}|/(2{\mathcal {U}})=1$ $x'$ $2\lambda c\cdot x^{*}$

QED (som skulle bevisas)

Avrandomisering med metoden för betingade sannolikheter

Lemmat ovan visar förekomsten av ett omslag till en uppsättning med kostnad ). I detta sammanhang är vårt mål en effektiv approximationsalgoritm, inte bara ett existensbevis, så vi har inte övervägt steg 3 färdigt. $O(\log(|{\mathcal {U}}|)c\cdot x^{*}$

Som ett tillvägagångssätt skulle man kunna öka lite och sedan visa att sannolikheten för framgång är minst, säg, 1/4. Genom att använda denna modifiering, upprepa det slumpmässiga avrundningssteget flera gånger, kan man säkerställa framgång med hög sannolikhet. $\lambda$

Detta tillvägagångssätt försvagar den garanterade effektiviteten, men vi kommer att beskriva ett annat tillvägagångssätt som ger en deterministisk algoritm som ger den garanterade effektiviteten som anges ovan. Tillvägagångssättet kallas metoden för betingade sannolikheter .

Den deterministiska algoritmen emulerar ett probabilistiskt avrundningsschema - varje uppsättning beaktas och istället för att välja slumpmässigt baserat på gör algoritmen ett deterministiskt val, så att den villkorade sannolikheten för misslyckande som bestäms av valet förblir mindre än 1 . $s\in {\mathcal {S))$ $x'_{s}\in \{0,1\}$ $x^{*}$

Begränsning för den villkorade sannolikheten för misslyckande

Vi vill kunna ställa in värdet på varje variabel för att hålla sannolikheten för villkorat misslyckande mindre än 1. För att uppnå detta behöver vi en bra gräns för sannolikheten för villkorat misslyckande. Gränsen erhålls genom att återbesöka det ursprungliga beviset på existens. Detta bevis begränsar implicit sannolikheten för misslyckande till det förväntade värdet av den slumpmässiga variabeln ${\displaystyle x'_{s))$

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

var

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

är uppsättningen element som lämnas utan täckning.

Den slumpmässiga variabeln kan tyckas något mystisk, men den återspeglar det systematiska tillvägagångssättet med probabilistiska bevis. Den första termen i formeln för erhålls genom att tillämpa Markovs ojämlikheter på sannolikheten för den första dåliga händelsen (kostnaden är för hög). Denna medlem bidrar med minst 1 till om priset är för högt. Den andra termen räknar antalet dåliga händelser av det andra slaget (avtäckta element). Det bidrar med minst 1 till om det lämnar något element oskyddat. Således, i varje utdata som är mindre än 1, måste lösningen täcka alla element och ha ett pris som överensstämmer med den önskade gränsen från lemma. Kortfattat, om avrundningssteget misslyckas, . Detta innebär (enligt Markovs ojämlikhet ) vad som är en övre gräns för sannolikheten för misslyckande. Observera att ovanstående argument redan är implicit närvarande i beviset på lemma, vilket också visar att . $F$ $F$ $F$ $x'$ $F$ $x'$ $F$ $x'$ $F\geq 1$ $E[F]$ $E[F]<1$

För att tillämpa den villkorade sannolikhetsmetoden måste vi utöka resonemanget för att begränsa den villkorade sannolikheten för misslyckande under avrundningssteget. Detta kan vanligtvis göras systematiskt, även om det kan vara tekniskt tidskrävande.

Så, vad är den villkorade sannolikheten för misslyckande när avrundningssteget går genom seten? Eftersom i vilket resultat som helst betyder att avrundningssteget ledde till misslyckande, enligt Markovs ojämlikhet , överstiger den villkorade sannolikheten för misslyckande inte den villkorade förväntan . $F\geq 1$ $F$

Vi beräknar sedan det villkorade medelvärdet , precis som vi beräknade medelvärdet i det ursprungliga beviset. Tänk på tillståndet för avrundningsprocessen i slutet av varje iteration . Låt beteckna de skannade uppsättningarna (de första uppsättningarna i ). Låt beteckna en (delvis tilldelad) vektor (så definierad endast om ). För en sådan uppsättning , låt beteckna sannolikheten med vilken den kommer att tilldelas till 1. Låt innehålla avslöjade element. Sedan den villkorade förväntan som ges av valet, d.v.s. ges av beslutet , då $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}+\summa _{s\not \in S^{(t)}}c(s)p_{s}}{2\lambda c\cdot x^{*}}}~+~\summa _{e\in {\ mathcal {U}}^{(t)}}\prod _{s\not \in S^{(t)},s\ni e}(1-p_{s}).

Observera att det bara definieras efter iterationen av . $E[F|x^{(t)}]$ $t$

Att hålla den villkorade sannolikheten för misslyckande mindre än 1

För att hålla den villkorade sannolikheten för misslyckande mindre än 1 räcker det att hålla det villkorliga medelvärdet mindre än 1. För att göra detta räcker det för att undvika tillväxten av det villkorliga medelvärdet, och det är vad algoritmen kommer att göra. Algoritmen kommer att ställas in vid varje iteration så att $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

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

Hur kan algoritmen ställas in på en iteration ? Det visar sig att du bara kan ställa in den för att efterlikna värdet på . $t$ $x'_{s'}$ $E[F|x^{(t)}]\leq E[F|S^{(t-1)}]$ $x'_{s'}$ $E[F|x^{(t)}]$

För att förstå varför, överväg tidpunkten när iterationen börjar. Vid denna tidpunkt är värdet definierat, men värdet är odefinierat - det kan anta två möjliga värden, beroende på hur det ställs in i iterationen . Låt betyder värde . Låt och beteckna två möjliga värden på , beroende på om den är satt till 0 eller 1. Enligt definitionen av den villkorade förväntan, $t$ $E[F|x^{(t-1)}]$ $E[F|x^{(t)}]$ $x'_{s'}$ $t$ ${\displaystyle E^{(t-1)))$ $E[F|x'^{(t-1)}]$ ${\displaystyle E_{0}^{(t)))$ ${\displaystyle E_{1}^{(t)))$ $E[F|x^{(t)}]$ $x'_{s'}$

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

Eftersom det vägda medelvärdet av två kvantiteter alltid är större än eller lika med den minsta av dem, följer det att

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

Således, inställning för att minimera det resulterande värdet på , säkerställer att . Detta är vad algoritmen kommer att göra. $x'_{s'}$ $E[F|x^{(t)}]$ $E[F|x^{(t)}]\leq E[F|x^{(t-1)}]$

I detalj, vad betyder detta? Betraktad som en funktion av (med alla andra fasta värden) är denna funktion linjär i , och koefficienten vid i denna funktion är $E[F|x^{(t)}]$ $x'_{s'}$ $x'_{s'}$ $x'_{s'}$

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

Algoritmen bör alltså ställas in på 0 om detta uttryck är positivt, och till 1 annars. Allt detta ger följande algoritm. $x'_{s'}$

Probabilistisk avrundningsalgoritm för uppsättningstäckning

input: uppsättning uppsättningar , befolkning , prisvektor ${\mathcal {S))$ ${\mathcal {U}}$ $c$

output: ställ in täckning (lösning av ett linjärt standardprogram med heltalsproblem för att täcka en sats) $x'$

Vi beräknar uppsättningens bråkdel med lägsta kostnad (den optimala lösningen av motsvarande linjära programmeringsproblem). $x^{*}$
Vi tilldelar . Vi tilldelar för ev . $\lambda \leftarrow \ln(2|{\mathcal {U}}|)$ $p_{s}\leftarrow \min(\lambda x_{s}^{*},1)$ $s\in {\mathcal {S))$
För allt vi gör: $s'\in {\mathcal {S))$
1. Vi tilldelar . ( innehåller set för vilka något beslut ännu inte har fattats.) ${\mathcal {S}}\leftarrow {\mathcal {S}}-\{s'\}$ ${\mathcal {S))$
2. Om en ${\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})$ sedan tilldelar vi $x'_{s}\leftarrow 0$ i annat fall tilldela och . $x'_{s}\leftarrow 1$ ${\mathcal {U}}\leftarrow {\mathcal {U}}-s'$ ( innehåller element som ännu inte täcks.) ${\mathcal {U}}$
Vi återvänder . $x'$

Lemma (garanterad effektivitet av algoritmen) Ovanstående algoritm returnerar ett uppsättningsskydd med ett pris som inte med en faktor överstiger minimipriset för ett (delat) setomslag.

x'

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

Bevis

Algoritmen säkerställer att den villkorade förväntan inte ökar vid varje iteration. Eftersom denna villkorade förväntan ursprungligen var mindre än 1 (som visas ovan), säkerställer algoritmen att den villkorade förväntningen förblir mindre än 1. Eftersom den villkorade sannolikheten för misslyckande inte överstiger den villkorade förväntan , säkerställer algoritmen att den villkorade sannolikheten för misslyckande kvarstår mindre än 1. Således, i slutet av algoritmen, när alla element är definierade, får algoritmen ett framgångsrikt resultat. Det vill säga, ovanstående algoritm returnerar ett uppsättningsskydd med ett pris som inte med en faktor överstiger minimipriset för varje (delvis) uppsättningsskydd. $F=E[F\,|\,x^{(t)}]$ $F$ $x'$ $2\ln(2|{\mathcal {U}}|)$

Anmärkningar om algoritmen

I exemplet ovan baserades algoritmen på den villkorade förväntan av en slumpvariabel . I vissa fall, istället för den exakta villkorade förväntan, används den övre gränsen (och ibland den nedre gränsen) för den villkorade förväntan på ett visst värde. Detta kallas en pessimistisk uppskattning . $F$

Se även

Villkorlig sannolikhetsmetod

Litteratur

Rajeev Motwani, Prabhakar Raghavan. Randomiserade algoritmer . - Cambridge University Press , 1995. - ISBN 978-0-521-47465-8 .
Vijay Vazirani. Approximationsalgoritmer . - Springer Verlag , 2001. - ISBN 978-3-540-65367-7 .
Prabhakar Raghavan, Clark D. Thompson. Randomiserad avrundning: En teknik för bevisligen bra algoritmer och algoritmiska bevis // Combinatorica . - 1987. - T. 7 , nr. 4 . — S. 365–374 . - doi : 10.1007/BF02579324 .
Prabhakar Raghavan. Probabilistisk konstruktion av deterministiska algoritmer: approximering av heltalsprogram // Journal of Computer and System Sciences . - 1988. - T. 37 , nr. 2 . — S. 130–143 . - doi : 10.1016/0022-0000(88)90003-7 .

Länk

Ingo Althofer. Om sparsamma approximationer till randomiserade strategier och konvexa kombinationer // Linjär algebra och dess tillämpningar. - 1994. - T. 199 . — S. 339–355 . - doi : 10.1016/0024-3795(94)90357-3 .
Thomas Lefmann, Hanno Lefmann. Beräkning av glesa approximationer deterministiskt // Linjär algebra och dess tillämpningar. - 1996. - T. 240 . — S. 9–19 . - doi : 10.1016/0024-3795(94)00175-8 .
Richard J. Lipton, Neal E. Young. Enkla strategier för stora nollsummespel med tillämpningar till komplexitetsteori // STOC '94: Proceedings of the twenty-sexth annual ACM symposium on theory of computing. - New York, NY: ACM , 1994. - S. 734-740. — ISBN 0-89791-663-8 . - doi : 10.1145/195058.195447 .