Rotunjire probabilistică

În informatică și cercetarea operațională, multe probleme de optimizare combinatorie sunt insolubile din punct de vedere computațional pentru a rezolva problema exact (adică pentru a obține soluția optimă). Multe astfel de probleme permit algoritmi de aproximare rapidă ( în timp polinomial ) - adică algoritmi care sunt garantat să returneze o soluție aproape optimă pentru orice intrare.

Rotunjirea probabilistică [1] este o abordare larg utilizată pentru dezvoltarea și analiza unor astfel de algoritmi de aproximare [2] [3] . Ideea de bază este utilizarea unei metode probabilistice pentru a transforma soluția optimă corespunzătoare a unei probleme de programare liniară (LP) într-o aproximare a soluției optime a problemei inițiale.

Prezentare generală

Abordarea de bază are trei pași:

Formulăm problema ca o problemă de programare liniară întreagă (ILP).
Calculăm soluția optimă fracțională a problemei de programare liniară (fără condiția întregului). $X$
Rotunjim soluția fracțională a problemei de programare liniară la soluția problemei întregi LP. $X$ $X'$

(Deși abordarea utilizează în principal programarea liniară, pot fi utilizate și alte tipuri de relaxare a condițiilor. De exemplu, algoritmul lui Goeman și Williamson utilizează algoritmul de tăiere maximă aproximativă de programare semidefinită .)

Scopul primului pas este de a alege o declarație adecvată a problemei de programare liniară întregi. Acest lucru necesită o bună cunoaștere a programării liniare și, în special, o înțelegere a modului de modelare a problemelor folosind programarea liniară și programarea liniară întregi. Cu toate acestea, pentru multe probleme există o problemă de programare liniară cu numere întregi naturale cu performanțe bune, așa cum se arată în exemplul problemei care acoperă setul. (O problemă de programare liniară cu numere întregi ar trebui să aibă un decalaj mic între întregi. În plus, rotunjirea probabilistică este adesea folosită pentru a demonstra decalajele întregi.)

În a doua etapă, soluția optimă fracțională, de obicei, poate fi calculată în timp polinomial folosind un algoritm de programare liniară standard .

La a treia etapă, soluția fracțională trebuie transformată într-o soluție întreagă (și astfel în soluția problemei inițiale). Acest proces se numește rotunjire fracționată a soluției . Soluția finală întreagă trebuie (în mod dovedibil) să aibă un preț care nu diferă mult de prețul soluției fracționale. Acest lucru asigură că costul unei soluții întregi nu este cu mult mai mare decât costul unei soluții întregi optime.

Tehnica principală folosită în a treia etapă (rotunjire) este utilizarea unei abordări probabilistice și apoi utilizarea raționamentului probabilistic pentru a limita creșterea prețului care vine odată cu rotunjirea. Aici argumentele probabilistice sunt folosite pentru a arăta existența unei structuri discrete cu proprietăți dorite. În acest context, argumentele probabilistice sunt folosite pentru a arăta următoarele:

Având în vedere o soluție fracțională a problemei LP, rotunjirea probabilistică cu probabilitate pozitivă dă o soluție întreagă care se aproximează

X

X'

X

conform unui criteriu dorit.

În cele din urmă, pentru a face al treilea pas eficient din punct de vedere computațional, fie se arată a fi aproape de cu probabilitate mare (astfel încât pasul să rămână probabilist), fie pasul de rotunjire este derandomizat , de obicei prin probabilități condiționate . Această din urmă metodă transformă procesul de rotunjire probabilistică într-un proces determinist eficient care este garantat să ofere un rezultat bun. $X'$ $X$

Comparație cu alte aplicații ale metodei probabilistice

Etapa de rotunjire probabilistică diferă de majoritatea aplicațiilor metodei probabilistice în două privințe:

Complexitatea de calcul a etapei de rotunjire este importantă. Pasul trebuie implementat de un algoritm rapid (adică un algoritm de timp polinomial ).
Distribuția de probabilitate care stă la baza unui experiment aleator este o funcție a soluției unei instanțe a unei probleme de programare liniară. Acest fapt este decisiv pentru demonstrarea eficienței garantate a algoritmului de aproximare. Adică, pentru orice instanță a problemei, algoritmul returnează o soluție care aproximează soluția optimă pentru acea instanță particulară . În comparație, aplicațiile metodei probabilistice în combinatorică arată de obicei existența unor structuri ale căror proprietăți depind de parametrii de intrare. De exemplu, luați în considerare teorema lui Turan , care poate fi enunțată ca „orice graf cu vârfuri și grad mediu trebuie să aibă un set independent de dimensiuni de cel puțin ”. (Vezi articolul „ Metoda probabilităților condiționate ” pentru o demonstrație probabilistică a teoremei lui Turán.) Deși există grafice pentru care această limită este exactă, există și grafice care au seturi independente mult mai mari decât . Astfel, dimensiunea unei mulțimi independente care există într-un graf conform teoremei lui Turan poate fi, în general, mult mai mică decât mulțimea independentă maximă a grafului. $X$ $n$ $d$ $n/(d+1)$ $n/(d+1)$

Un exemplu de coperta set

Metoda este cel mai bine ilustrată cu un exemplu. Următorul exemplu arată modul în care rotunjirea aleatoare poate fi utilizată pentru a crea un algoritm de aproximare pentru problema setului de acoperire .

Luați orice exemplu al problemei de acoperire a setului cu colecția . $\langle c,{\mathcal {S}}\rangle$ ${\mathcal {U}}$

Pentru pasul 1, să fie problema întregului LP să fie problema standard de programare liniară întregă pentru a acoperi mulțimea .

Pentru pasul 2, să fie problema LP slăbirea problemei ILP la problema LP și să fie soluția optimă pentru această problemă slăbită obținută de orice algoritm de programare liniară standard . (Timpul necesar pentru rezolvarea problemei LP depinde polinom de mărimea intrării.) $x^{*}$

(Soluțiile valide ale problemei LP sunt vectori care atribuie fiecărei mulțimi o greutate nenegativă , astfel încât, pentru orice element , acoperă - greutatea totală atribuită mulțimilor care conțin , este cel puțin 1, adică $X$ $s\in {\mathcal {S)}$ $x_{s}$ $e\in {\mathcal {U}}$ $X'$ $e$ $e$

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

O soluție optimă este o soluție fezabilă al cărei cost este $x^{*}$

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

cât mai mic posibil.)

Rețineți că orice capac al setului pentru oferă o soluție fezabilă (unde pentru , în caz contrar). Prețul acestei acoperiri este egal cu prețul , adică ${\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}.

Cu alte cuvinte, problema de programare liniară este o relaxare a problemei de acoperire a mulțimii date.

Deoarece are prețul minim dintre soluțiile fezabile ale problemei LP, prețul este limita inferioară pentru costul acoperirii optime a setului . $x^{*}$ $x^{*}$

Pasul 3: rotunjire aleatorie

Mai jos este o descriere a descrierii celui de-al treilea pas, pasul de rotunjire, care trebuie să transforme acoperirea parțială a prețului minim stabilit într-o soluție întregă validă (corespunzând acoperirii setate corecte). $x^{*}$ $X'$

Pasul de rotunjire va da o soluție , care, cu probabilitate pozitivă, are un preț care diferă de preț printr-un factor mic. Apoi (deoarece prețul este limita inferioară a prețului acoperirii setului optim), prețul va diferi de prețul optim printr-un factor mic. $X'$ $x^{*}$ $x^{*}$ $X'$

Ca punct de plecare, luați în considerare cea mai naturală schemă de rotunjire:

Pentru fiecare set pe rând, luăm cu probabilitate , altfel luăm .

s\in {\mathcal {S)}

x'_{s}=1

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

x'_{s}=0

Conform acestei scheme de rotunjire, așteptarea matematică a prețului setului selectat nu depășește , prețul acoperirii parțiale. Acest lucru este bun, dar, din păcate, acoperirea nu este bună. Dacă variabilele sunt mici, probabilitatea ca elementul să nu fie acoperit este aproximativă $\sum _{s}c(s)x_{s}^{*}$ $x_{s}^{*}$ $e$

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

Astfel, așteptarea matematică a proporției elementelor acoperite va fi constantă.

Pentru a face foarte probabil să acopere toate elementele, schema standard de rotunjire crește mai întâi probabilitățile de rotunjire cu un factor adecvat . Schema standard de rotunjire: $X'$ $\lambda >1$

Fixăm parametrul . Pentru fiecare set ,

\lambda \geq 1

s\in {\mathcal {S)}

luăm cu probabilitate , altfel luăm .

x'_{s}=1

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

x'_{s}=0

Înmulțirea probabilităților cu crește valoarea așteptată a prețului cu , dar face ca acoperirea tuturor elementelor să fie mai probabilă. Ideea aici este să alegeți cât mai mic posibil, astfel încât toate elementele să fie acoperite cu probabilitate diferită de zero. Mai jos este o analiză detaliată. $\lambda$ $\lambda$ $\lambda$

Lema (eficiența garantată a schemei de rotunjire) Reparăm . Cu o probabilitate pozitivă, schema de rotunjire va returna o acoperire cu un cost care nu depășește (și acest cost diferă printr-un factor al costului acoperirii setate optime).

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

X'

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

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

(Rețineți că, cu puțină atenție, valoarea poate fi redusă la .) $O(\log |{\mathcal {U}}|)$ $\ln(|{\mathcal {U}}|)+O(\log \log |{\mathcal {U}}|)$

Dovada

Ieșirea schemei de rotunjire aleatorie are proprietățile dorite până când apar următoarele evenimente „rele”: $X'$

pretul solutiei va depasi $c\cdot x'$ $X'$ $2\lambda c\cdot x^{*}$
pentru un element , nu acoperă . $e$ $X'$ $e$

Așteptările matematice ale fiecăruia nu depășesc . Datorită liniarității așteptării matematice , așteptarea nu depășește . Apoi, conform inegalității Markov , probabilitatea primului eveniment rău nu depășește . $x'_{s)$ $\lambda x_{s}^{*}$ $c\cdot x'$ $\sum _{s}c(s)\lambda x_{s}^{*}=\lambda c\cdot x^{*}$ $1/2$

Pentru evenimentele proaste rămase (câte unul pentru fiecare element al lui ), rețineți că deoarece , pentru orice element dat al lui , probabilitatea care nu este acoperită este $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}}

(Aici folosim inegalitatea , care este strict adevărată pentru .) $1+z\leq e^{z}$ $z\neq 0$

Astfel, pentru orice număr de elemente, probabilitatea ca elementul să nu fie acoperit este mai mică decât . $|{\mathcal {U}}|$ $1/(2{\mathcal {U}})$

Probabilitatea ca unul dintre evenimentele rele să se întâmple este mai mică . Apoi, probabilitatea absenței evenimentelor rele este mai mare decât zero și este o acoperire a setului cu un cost care nu depășește . $1+|{\mathcal {U}}|$ $1/2+|{\mathcal {U}}|/(2{\mathcal {U}})=1$ $X'$ $2\lambda c\cdot x^{*}$

QED (care urma să fie dovedit)

Derandomizarea prin metoda probabilităților condiționate

Lema de mai sus arată existența unei acoperiri a unei mulțimi cu cost ). În acest context, scopul nostru este un algoritm de aproximare eficient, nu doar o dovadă a existenței, așa că nu am terminat de analizat pasul 3. $O(\log(|{\mathcal {U}}|)c\cdot x^{*}$

Ca o abordare, ar putea crește puțin și apoi arăta că probabilitatea de succes este de cel puțin, să zicem, 1/4. Folosind această modificare, repetând pasul de rotunjire aleatorie de mai multe ori, se poate asigura succesul cu o mare probabilitate. $\lambda$

Această abordare slăbește eficiența garantată, dar vom descrie o altă abordare care dă un algoritm determinist care oferă eficiența garantată indicată mai sus. Abordarea se numește metoda probabilităților condiționate .

Algoritmul determinist emulează o schemă de rotunjire probabilistică — fiecare mulțime este luată în considerare și , totuși, în loc să aleagă aleatoriu pe baza , algoritmul face o alegere deterministă , astfel încât probabilitatea condiționată de eșec determinată de alegere să rămână mai mică de 1 . $s\in {\mathcal {S)}$ $x'_{s}\in \{0,1\}$ $x^{*}$

Constrângere asupra probabilității condiționate de eșec

Dorim să putem seta valoarea fiecărei variabile pentru a menține probabilitatea de eșec condiționată mai mică de 1. Pentru a realiza acest lucru, avem nevoie de o limită bună a probabilității de eșec condiționată. Granița se obține prin revizuirea dovezii originale a existenței. Această dovadă limitează implicit probabilitatea de eșec la valoarea așteptată a variabilei aleatoare $x'_{s)$

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

Unde

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

este ansamblul elementelor rămase neacoperite.

Variabila aleatoare poate părea oarecum misterioasă, dar reflectă abordarea sistematică a demonstrației probabilistice. Primul termen din formula pentru este obținut prin aplicarea inegalităților lui Markov la limita de probabilitate pentru primul eveniment rău (costul este prea mare). Acest membru contribuie cu cel puțin 1 dacă prețul este prea mare. Al doilea termen numără numărul de evenimente rele de al doilea fel (elemente neacoperite). Contribuie cu cel puțin 1 la dacă lasă orice element neacoperit. Astfel, în orice ieșire care este mai mică de 1, soluția trebuie să acopere toate elementele și să aibă un preț compatibil cu limita dorită din lemă. Pe scurt, dacă pasul de rotunjire eșuează, . Aceasta implică (conform inegalității lui Markov ) care este o limită superioară a probabilității de eșec. Rețineți că argumentele de mai sus sunt deja implicit prezente în demonstrația lemei, ceea ce arată și că . $F$ $F$ $F$ $X'$ $F$ $X'$ $F$ $X'$ $F\geq 1$ $E[F]$ $E[F]<1$

Pentru a aplica metoda probabilității condiționate, trebuie să extindem raționamentul pentru limitarea probabilității condiționate de eșec în timpul etapei de rotunjire. Acest lucru se poate face de obicei în mod sistematic, deși din punct de vedere tehnic poate consuma mult timp.

Deci, care este probabilitatea condiționată de eșec atunci când pasul de rotunjire trece prin mulțimi? Deoarece în orice rezultat înseamnă că pasul de rotunjire a condus la eșec, conform inegalității lui Markov , probabilitatea condiționată de eșec nu depășește așteptarea condiționată . $F\geq 1$ $F$

Apoi calculăm media condiționată , așa cum am calculat media în demonstrația inițială. Luați în considerare starea procesului de rotunjire la sfârșitul fiecărei iterații . Să notăm seturile scanate (primele seturi în ). Să notăm un vector (alocat parțial) ( definit astfel doar dacă ). Pentru o astfel de mulțime , denotăm probabilitatea cu care va fi atribuită la 1. Fie conține elemente neacoperite. Apoi așteptarea condiționată dată de alegere, adică dată de decizie , atunci $F$ $F$ $t$ $S^{{(t)}}$ $t$ ${\mathcal {S)}$ $x^{(t))$ $X'$ $x_{s}^{(t))$ $s\in S^{(t))$ $s\nu \in S^{(t))$ $p_{s}=\min(\lambda x_{s}^{*},1)$ $x'_{s)$ ${\mathcal {U}}^{(t))$ $F$ $x^{(t))$

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

Rețineți că este definit numai după iterația lui . $E[F|x^{(t)}]$ $t$

Menținerea probabilității condiționate de eșec mai mică de 1

Pentru a menține probabilitatea condiționată de eșec mai mică de 1, este suficient să păstrați media condiționată mai mică de 1. Pentru a face acest lucru, este suficient să evitați creșterea mediei condiționate și asta va face algoritmul. Algoritmul se va seta la fiecare iterație astfel încât $F$ $F$ $x'_{s)$

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

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

La o iterație , cum se poate seta algoritmul la ? Se pare că îl puteți seta doar să imite valoarea lui . $t$ $x'_{s'}$ $E[F|x^{(t)}]\leq E[F|S^{(t-1)}]$ $x'_{s'}$ $E[F|x^{(t)}]$

Pentru a înțelege de ce, luați în considerare momentul în care începe iterația. În acest moment, valoarea este definită, dar valoarea este nedefinită - poate lua două valori posibile, în funcție de modul în care este setată în iterație . Lasa înseamnă valoare . Fie și notăm două valori posibile ale lui , în funcție de faptul că este setată la 0 sau la 1. Prin definiția așteptării condiționate, $t$ $E[F|x^{(t-1)}]$ $E[F|x^{(t)}]$ $x'_{s'}$ $t$ $E^{(t-1))$ $E[F|x'^{(t-1)}]$ $E_{0}^{(t))$ $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)}.

Deoarece media ponderată a două cantități este întotdeauna mai mare sau egală cu cea mai mică dintre ele, rezultă că

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

Astfel, setarea astfel încât să minimizeze valoarea rezultată a , asigură că . Aceasta este ceea ce va face algoritmul. $x'_{s'}$ $E[F|x^{(t)}]$ $E[F|x^{(t)}]\leq E[F|x^{(t-1)}]$

În detaliu, ce înseamnă asta? Considerată ca o funcție a (cu toate celelalte valori fixe), această funcție este liniară în , iar coeficientul at în această funcție este $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\not \in S^{(t)},s\ni e}(1-p_{s}).

Astfel, algoritmul ar trebui setat la 0 dacă această expresie este pozitivă și la 1 în caz contrar. Toate acestea dau următorul algoritm. $x'_{s'}$

Algoritm de rotunjire probabilistică pentru acoperirea setului

intrare: set de mulțimi , populație , vector preț ${\mathcal {S)}$ ${\mathcal {U}}$ $c$

ieșire: acoperire set (soluția unei probleme de programare liniară cu numere întregi standard pentru a acoperi un set) $X'$

Calculăm acoperirea fracțională a mulțimii cu costul minim (soluția optimă a problemei de programare liniară corespunzătoare). $x^{*}$
Noi atribuim . Atribuim pentru orice . $\lambda \leftarrow \ln(2|{\mathcal {U}}|)$ $p_{s}\leftarrow \min(\lambda x_{s}^{*},1)$ $s\in {\mathcal {S)}$
Pentru orice facem: $s'\in {\mathcal {S)}$
1. Noi atribuim . ( conține seturi pentru care încă nu a fost luată o decizie.) ${\mathcal {S}}\leftarrow {\mathcal {S}}-\{s'\}$ ${\mathcal {S)}$
2. În cazul în care un ${\frac {c_{s'}}{2\lambda c\cdot x^{*}}}>\sum _{e\in s'\cap {\mathcal {U}}}\prod _ {s\în {\mathcal {S}},s\ni e}(1-p_{s})$ apoi atribuim $x'_{s}\leftarrow 0$ în caz contrar, atribuiți și . $x'_{s}\leftarrow 1$ ${\mathcal {U}}\leftarrow {\mathcal {U}} -s'$ ( conține elemente neacoperite încă.) ${\mathcal {U}}$
Ne intoarcem . $X'$

Lema (eficiența garantată a algoritmului) Algoritmul de mai sus returnează o acoperire setată cu un preț care nu depășește cu un factor prețul minim al oricărei acoperiri setate (fracționale).

X'

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

Dovada

Algoritmul asigură că așteptarea condiționată nu crește la fiecare iterație. Deoarece această așteptare condiționată a fost inițial mai mică de 1 (așa cum se arată mai sus), algoritmul asigură că așteptarea condiționată rămâne mai mică de 1. Deoarece probabilitatea condiționată de eșec nu depășește așteptarea condiționată , algoritmul asigură că probabilitatea condiționată de eșec rămâne mai mic decât 1. Astfel, la sfârșitul algoritmului, când toate elementele sunt definite, algoritmul obține un rezultat de succes. Adică, algoritmul de mai sus returnează o acoperire setată cu un preț care nu depășește cu un factor prețul minim al oricărei acoperiri setate (fracționale). $F=E[F\,|\,x^{(t)}]$ $F$ $X'$ $2\ln(2|{\mathcal {U}}|)$

Note despre algoritm

În exemplul de mai sus, algoritmul s-a bazat pe așteptarea condiționată a unei variabile aleatoare . În unele cazuri, în locul așteptării condiționale exacte, este utilizată limita superioară (și uneori limita inferioară) a așteptării condiționate a unei anumite valori. Aceasta se numește estimare pesimistă . $F$

Vezi și

Metoda probabilității condiționate

Literatură

Rajeev Motwani, Prabhakar Raghavan. Algoritmi randomizati . - Cambridge University Press , 1995. - ISBN 978-0-521-47465-8 .
Vijay Vazirani. Algoritmi de aproximare . - Springer Verlag , 2001. - ISBN 978-3-540-65367-7 .
Prabhakar Raghavan, Clark D. Thompson. Rotunjire randomizată: O tehnică pentru algoritmi și dovezi algoritmice care se dovedesc buni // Combinatorica . - 1987. - T. 7 , nr. 4 . — S. 365–374 . - doi : 10.1007/BF02579324 .
Prabhakar Raghavan. Construcția probabilistică a algoritmilor determiniști: aproximarea programelor întregi de ambalare // Journal of Computer and System Sciences . - 1988. - T. 37 , nr. 2 . — S. 130–143 . - doi : 10.1016/0022-0000(88)90003-7 .

Link

Ingo Althofer. Despre aproximări rare ale strategiilor randomizate și combinațiilor convexe // Algebra liniară și aplicațiile sale. - 1994. - T. 199 . — S. 339–355 . - doi : 10.1016/0024-3795(94)90357-3 .
Thomas Lefmann, Hanno Lefmann. Calculul deterministic a aproximărilor rare // Algebra liniară și aplicațiile sale. - 1996. - T. 240 . — P. 9–19 . - doi : 10.1016/0024-3795(94)00175-8 .
Richard J. Lipton, Neal E. Young. Strategii simple pentru jocuri mari cu sumă zero cu aplicații la teoria complexității // STOC '94: Proceedings of the twoty-66th 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 .