Edmonds-Prus-pöytäkirja

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 12. tammikuuta 2021 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Edmonds–Prus- protokolla on reilu kakkuleikkausprotokolla . Sen tavoitteena on saada heterogeenisen resurssin osittain verrannollinen jako n henkilön kesken siten, että jokainen osallistuja saa kakun (palan) osajoukon, jonka kukin osallistuja arvioi vähintään 1/ an koko estimaatista, jossa on jokin riittävän suuri vakio . Algoritmi on todennäköisyydellä ajoajalla O( n ) onnistumistodennäköisyydellä lähellä 1. Protokollan kehittivät Jeff Edmond ja Kirk Prus, jota he myöhemmin paransivat Jaisingh Solankin kanssa. $a\geqslant 10$

Motivaatio

Kakun suhteellinen jako saadaan aikaan käyttämällä rekursiivista puolittamisalgoritmia ajassa . Jotkut tulokset monimutkaisuudesta osoittavat, että tämä ajoaika on optimaalinen useilla oletuksilla. Erityisesti rekursiivinen puolittaminen on nopein algoritmi täyden suhteellisuuden saamiseksi, kun palat on yhdistettävä, ja se on nopein mahdollinen deterministinen algoritmi jopa osittaisen suhteellisuuden saavuttamiseksi ja jopa silloin, kun se on sallittua leikata irrotettuihin osiin. On tapaus, jota monimutkaisuuden tulokset eivät kata, tämä on todennäköisyysalgoritmien tapaus, jotka takaavat vain osittaisen suhteellisuuden ja mahdollisuuden katketa osia . Edmonds-Prus-protokolla pyrkii tarjoamaan O( n ) käyntiajan juuri tätä tapausta varten. $O(n\log n)$

Protokolla

Yleinen kaavio Edmundsin ja Pruksen mukaan on seuraava [1] :

Jokainen osallistuja jakaa kakun yksityisesti identtisiksi paloiksi (subjektiivisen arvionsa mukaan). Näitä kappaleita kutsutaan ehdokaskappaleiksi . $n\cdot an$
Jokainen osallistuja valitsee 2 d ehdokaskappaletta yhtä suurella todennäköisyydellä ja tuotolla ( d on vakio ja määritellään myöhemmin). Ehdokkaat ryhmitellään d -pareihin, jotka osallistuja raportoi algoritmille. Näitä pareja kutsutaan neljännesvälierien yhdistämisiksi . $n\cdot d$
Algoritmi valitsee jokaisesta neljännesfinaalipaketista yhden kappaleen, sen, jolla on risteyksiä vähiten muiden ehdokkaiden kanssa. Näitä kappaleita kutsutaan semifinaalikappaleiksi . $n\cdot d$
Algoritmi valitsee jokaiselle osallistujalle yhden kappaleen, näitä kappaleita kutsutaan lopullisiksi . Viimeiset palat valitaan siten, että jokainen piste peittyy enintään kahdella viimeisellä palalla (katso alla). Jos tämä onnistuu, siirry vaiheeseen 5. Jos se epäonnistuu, palaa vaiheeseen 1.
Jokainen kakun osa, joka kuuluu vain yhteen loppukappaleeseen, annetaan kyseisen palan omistajalle. Jokainen kakun osa, joka kuuluu kahteen viimeiseen palaan, jaetaan suhteellisesti millä tahansa deterministisellä suhteellisella jakoalgoritmilla.

Algoritmi takaa, että suurella todennäköisyydellä jokainen osallistuja saa vähintään puolet ehdokaskappaleestaan, mikä tarkoittaa (jos preferenssifunktiot ovat additiivisia), että arvo on vähintään . ${\tfrac {an}{2))$

Vaiheessa #5 on O( n ) ehdokaskappaletta ja O( n ) lisäleikkausta, jotka vievät O(1) aikaa. Siksi algoritmin kokonaisajoaika on O( n ).

Tämän kaavion päätehtävä on viimeisten kappaleiden valinta vaiheessa #4:

Aloitetaan luomalla leikkauskuvaaja , graafi, jonka kärjet ovat puolifinaalipalat, ja kaari jäsenen i palasta I jäsenen j palaan J on olemassa, jos pala I leikkaa jäsenen j kappaleen J (siis jos valitsemme pala I ja haluamme välttää risteyksiä, meidän on valittava myös pala J ).

Valitaan mielivaltainen osallistuja i , joka ei ole vielä saanut palaansa, ja valitaan tämän osallistujan mielivaltainen pala I lopulliseksi kappaleeksi. Sitten käydään läpi leikkauskaavion yhteys ja valitaan lopullisiksi kappaleiksi kaikki palat, jotka saavutetaan kärjestä I . On olemassa kaksi hyvää skenaariota - joko jaamme yhden lopullisen palan kullekin osallistujalle ja näin suoritamme toimenpiteen tai saavutamme palan, jolla ei ole lähteviä linkkejä (eli se ei leikkaa muita kappaleita). Jälkimmäisessä tapauksessa valitsemme vain toisen kappaleen yhdestä jäljellä olevista jäsenistä ja jatkamme. Huono skenaario tapahtuu, kun matkamme johtaa kahteen eri palaan samaa jäsentä tai vastaavasti eri palaan jäsentä i , josta aloitimme matkan. Tällaista polkua, joka johtaa osallistujan i palasta saman osallistujan toiseen osaan, kutsutaan paripoluksi . Jos leikkausgraafi ei sisällä parillisia polkuja, niin kuvattu algoritmi palauttaa joukon n ei-päällekkäistä loppuosaa, ja meillä on haluttu tulos. Nyt on vielä laskettava todennäköisyys, että leikkauskaavio sisältää parillisen polun.

Harkitse ensin erikoistapausta, jossa kaikilla osallistujilla on samat mieltymystoiminnot (ja siten sama joukko ehdokaskappaleita). Tässä tapauksessa parillisen polun todennäköisyys on helppo laskea, koska jokaisen kaaren todennäköisyys on 1/ an ja kaikki reunat ovat riippumattomia, joten tietyn pituisen k parillisen polun todennäköisyys on , ja minkä tahansa kaaren todennäköisyys. parillinen polku on enintään: ${\displaystyle {\tfrac {1}{(an)^{k))))$

\sum _{k}{\frac {(2dn)!}{(2dn-k)!(an)^{k))}=O\left({\frac {1}{a^{2 }}}\oikea)

Valitsemalla d =1 ja riittävän suuren a , tämä todennäköisyys voidaan tehdä mielivaltaisen pieneksi. Tämä on totta, vaikka jätämme välierien valintavaiheen (nro 3) pois ja katsomme kaikki neljännesfinalistit semifinalisteiksi.

Huomaa, että tämä tapaus on samanlainen kuin pallot uurnassa mallissa . Tämä osoittaa, että jos kullekin pallolle valitaan mielivaltaisesti d urnaa, niin kullekin pallolle voidaan valita yksi uurna niin, että kaikki uurnat ovat erilaisia (pallojen enimmäismäärä on 1).

Yleisessä kakkumallissa, kun preferenssifunktiot ovat erilaiset, leikkauskaavion reunatodennäköisyydet ovat riippuvaisia, mutta puolifinalistien valintavaiheen ansiosta voimme osoittaa, että todennäköisyys, että leikkauskaavio sisältää parillisen polun, jonka pituus on vähintään 3 ei ylitä . ${\frac {32d^{5}}{a^{2}\cdot (a-4d^{2})))$

On vielä harkittava parillisia polkuja, joiden pituus on 2. Valitettavasti todennäköisyys saada tällainen parillinen polku leikkauskuvaajassa ei ole vähäpätöinen. Suurella todennäköisyydellä on kuitenkin mahdollista jakaa osallistujat kahteen ryhmään, joista kummallakaan ei ole paritettuja polkuja, joiden pituus on 2. Siksi voimme suorittaa lopullisten kappaleiden valinnan algoritmin kahdesti, kerran kullekin ryhmälle. Leikkaus voi tapahtua vain eri ryhmien lopullisten osien välillä, joten päällekkäisyys kakun kussakin kohdassa ei ylitä 2:ta. Todennäköisyys, että tällainen 2-osio on mahdoton , ei ylitä . ${\frac {16d^{3}}{a^{3}}}+{\frac {8d^{2}}{a^{2}}}$

Kun on laskettu yhteen kaksi yllä olevaa lauseketta ja otettu d = 2, saadaan, että epäonnistumisen todennäköisyys pysyy . Muista, että a on suhteellisuussuhde – mitä suuremman arvon haluamme taata kullekin osallistujalle, sitä todennäköisemmin jako epäonnistuu ja se tulee aloittaa vaiheesta 1. $O\left({\frac {1}{a^{2))}\right)$

Jotkut algoritmit toimivat myös, jos leikkaukset ovat likimääräisiä, eli osallistujat eivät tiedä, ovatko merkityt palat yhtä suuret. He voivat merkitä kappaleen, jonka p -prosenttiarvo on vaaditun arvon ylä- tai alapuolella, ja tarkka virhe valitaan satunnaisesti [1] .

High Confidence Protocol

Voit edelleen vähentää epäonnistumisen mahdollisuutta käyttämällä seuraavaa kaaviota [2] :

Suoritamme alkuperäisen protokollan kahdesti.
Jokaisella juoksulla poistamme kaikki osallistujat, jotka ovat parillisen polun alussa, ja jaamme lopulliset palat vain jäljellä olevien osallistujien kesken, kuten alkuperäisessä algoritmissa.
Jos jokaista jäsentä ei poistettu millään juoksulla, saimme mitä tarvitsimme, koska jokaisella jäsenellä on nyt yksi viimeinen pala.

Todennäköisyys tietyn osallistujan poistamiseen kustakin passista on . Tietyn osallistujan poistamisen todennäköisyys molemmilla ajoilla on yhtä suuri kuin . Siksi epäonnistumisen todennäköisyys on , ja se pyrkii nollaan n kasvaessa, vaikka osittaissuhteellisuussuhde a pidetään vakiona. $O\left({\frac {1}{n))\right)$ $O\left({\frac {1}{n^{2))}\oikea)$ $O\left({\frac {n}{n^{2}}}\right)=O\left({\frac {1}{n}}\oikea)$

Aiheeseen liittyviä kysymyksiä

Kakkumallia voidaan pitää palloongelmamallin yleistyksenä [ . Tätä mallia käytetään laajasti esimerkiksi kuormituksen tasapainottamisessa . Näissä tilanteissa pallo edustaa työtä, joka voidaan osoittaa erilaisille koneille (terminologiamme mukaan uurnat). Karkeasti sanottuna identtisten koneiden kuorman jakautuminen on palloja ja uurnoja, ja epätasaisten koneiden kuorman jakautuminen leikkaa kakkua. Siksi on aivan selvää, että kakkumallilla ja Edmonds-Prus-protokollalla pitäisi olla mielenkiintoisia sovelluksia kuormituksen jakautumisen kannalta erilaisissa koneissa [1] .

Muistiinpanot

↑ 1 2 3 Edmonds, Pruhs, 2006 , s. 623.
↑ Edmonds, Pruhs, Solanki, 2008 , s. 155-164.

Kirjallisuus

Jeff Edmonds, Kirk Pruhs. Balanced Allocations of Cake // 2006 47. vuotuinen IEEE-symposium tietojenkäsittelytieteen perusteista (FOCS'06). - 2006. - ISBN 978-0-7695-2720-8 . - doi : 10.1109/focs.2006.17 .
Jeff Edmonds, Kirk Pruhs, Jaisingh Solanki. Kakun leikkaaminen itsevarmasti suunnilleen reiluiksi paloiksi // Algoritmiset näkökohdat tiedossa ja hallinnassa. - 2008. - T. 5034. - (Luentomuistiinpanot tietojenkäsittelytieteestä). - ISBN 978-3-540-68865-5 . - doi : 10.1007/978-3-540-68880-8_16 .