il problema del minimo albero ricoprente in un grafo con archi privati
TRANSCRIPT
![Page 1: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/1.jpg)
Il problema del minimo albero ricoprente
in un grafo con archi privati
![Page 2: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/2.jpg)
Un problema molto noto…
INPUT: G=(V,E): grafo non diretto pesato, w(e)R+ per ogni e E
T è un albero ricoprente di G se:1. T è un albero2. T è un sottografo di G3. T contiene tutti i nodi di G
OUTPUT: T=(V,ET) minimo albero ricoprente di
G, ovvero che minimizza il peso totale w(T)= w(e)
e ET
![Page 3: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/3.jpg)
Scenario
Archi di un grafo controllati da agenti egoistici Solo l’agente conosce il peso associato al
proprio arco Obiettivo: calcolare una “buona” soluzione di
un certo problema di ottimizzazione rispetto a pesi reali
Strumento: progettazione di un meccanismo truthful (pagamento opportuno degli agenti per convincerli a dire la verità!)
![Page 4: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/4.jpg)
Il problema del minimum spanning tree (MST) egoistico
Input: un grafo G=(V,E), ogni arco è un agente egoistico, un nodo sorgente s e un nodo destinazione t; il tipo di un agente è il costo di utilizzo dell’arco (quindi tipo > 0); la sua valutazione è uguale al suo tipo;
SCF: un vero MST di G=(V,E,tipi).
![Page 5: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/5.jpg)
Più Formalmente Soluzioni ammissibili:
F: insieme degli alberi ricoprenti di G Tipo dell’agente e:
e: peso dell’arco intuitivamente: e è il costo che l’agente
sostiene per utilizzare e Valutazione agente e di un albero
ricoprente TF : ve(e,T)= e se eE(T), 0 altrimenti
SCF: minimo albero ricoprente di G=(V,E,)
![Page 6: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/6.jpg)
Come progettare un meccanismo truthful per il
problema?Osservazione cruciale:
il (vero) peso di un albero ricoprente T è:
eE ve(e,T)
problema utilitario!
…usiamo i meccanismi VCG
![Page 7: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/7.jpg)
Meccanismo VCG
M= <g(r), p(x)>: g(r): arg minxF j vj(rj,x)
pe(x): Per ogni arco eE:
pe =j≠e vj(rj,g(r-e)) -j≠e vj(rj,x) cioè
![Page 8: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/8.jpg)
Meccanismo VCG M= <g(r), p(x)>:
g(r): dato il grafo G e le dichiarazioni r=(r1,…,rm), calcola il MST T=(V,ET) di G=(V,E,r)
pe: Per ogni arco e E, pe =j≠e vj(rj,x(r-e)) -j≠e vj(rj,x) cioè
pe=w(TG-e)-w(T)+ re se eET,
pe=0 altrimenti.
dove TG-e è il MST di rimpiazzo per e (MST di G-e=(V,E\{e},r-e))
Ipotesi di lavoro: Grafo 2-edge connesso (altrimenti TG-e potrebbe non esistere
il possessore dell’arco e “terrebbe in pugno” il sistema!)
![Page 9: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/9.jpg)
Quel è la complessità temporale del meccanismo?
…dobbiamo calcolare con un MST di G
…e il pagamento per gli archi selezionati
Miglior algoritmo centralizzato richiede tempo O(m (m,n))
![Page 10: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/10.jpg)
Una soluzione banale
e T applichiamo l’algoritmo di calcolo dell’MST al grafo G-e
Complessità: n-1 archi dell’MST per O(m (m,n)): O(nm (m,n))
La soluzione efficiente che proponiamo costerà ancora O(m (m,n))!!!
![Page 11: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/11.jpg)
La funzione di Ackermann A(i,j) e la sua inversa (m,n)
![Page 12: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/12.jpg)
A(i,j) per piccoli valori di i e j
2 23 24
22
22
222222
222222
22222
216
22
22
2
216
22
22
2
222
2 16
... ..
... ..
..
..
j=1 j=2 j=3 j=4
i=1
i=2
i=3
![Page 13: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/13.jpg)
La funzione (m,n)
![Page 14: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/14.jpg)
Proprietà
1. Fissato n, (m,n) è monotonicamente decrescente al crescere di m
(m,n)= min {i>0 : A(i, m/n) > log2 n}
crescente in m
2. (n,n) per n
(n,n)= min {i>0 : A(i, n/n) > log2 n} = min {i>0 : A(i, 1) > log2 n}
![Page 15: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/15.jpg)
(m,n) 4 per ogni scopo pratico (cioè per valori di n ragionevoli)
A(4,m/n) A(4,1) = A(3,2)
=22
2 16.. .
>> 1080
numero stimato di atomi nell’universo osservabile
(m,n)= min {i>0 : A(i, m/n) > log2 n}
Osservazione
quindi (m,n) 4 per ogni n<21080
![Page 16: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/16.jpg)
Un po’ di storia
1926: Boruvka riscoperto da: Choquete, 1938 Florek et. al., 1951 Sollin, 1961 (l’articolo di
Boruvka era ormai conosciuto!)
1930: Jarnìk riscoperto da: Prim, 1957 Dijkstra, 1959
1956: Kruskal riscoperto da: Loberman e Weinberg,
1956, qualche mese dopo
…e le complessità temporali di
questi algoritmi?
…raramente menzionatenegli articoli…
Esempi:Quick Sort è del ’61, Hoare
Heap binari del ’64, Williams
![Page 17: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/17.jpg)
Complessità temporali 1975: Yao - O(m loglogn)
linear time selection di Blum et al. (1972) 1975: Johnson O(m logd n)
d=max{m/n,2} d-heaps (Johnson 1975)
1976: Cheriton e Tarjan – O(m log logd n) Mergeable leftist heaps di Crane (1972)
1984: Fredman e Tarjan – O(m log*(m,n)) Heap di Fibonacci di Fredman e Tarjan (1984)
1986: Gabow, Galil, Spencer, Tarjan – O(mloglog*(m,n))
Usando meglio gli heap di Fibonaccilog*(m,n)= 1+log*n-log*(m/n)
…tutti usano un approccio greedy…
![Page 18: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/18.jpg)
Perché l’approccio greedy: una proprietà forte
Dato G=(V,E), grafo non orientato
F = {FE: F non contiene cicli}
(E, F ): matrioide grafico
![Page 19: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/19.jpg)
Complessità temporali 1997: Chazelle - O(m (m,n) log (m,n))
Soft-heap di Chazelle (1997) 2000: Chazelle O(m (m,n))
Miglior uso dei Soft-heap 2002: Pettie e Ramachandran –
O(MST*(m,n)) dove MST*(m,n): complessità dell’albero di
decisione del problema del minimo albero ricoprente (numero minimo di confronti nel caso peggiore)
MST*(m,n)= O(m (m,n)) e MST*(m,n)= (m)
![Page 20: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/20.jpg)
Un problema aperto
MST*(m,n) = O(m)?
![Page 21: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/21.jpg)
Un problema correlato: verifica di un MST
Input: grafo G=(V,E) pesato non orientato, T=(V,ET) albero ricoprente di G
Domanda: T è un MST per G?
![Page 22: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/22.jpg)
Verifica di un MST
6
2
7
1
9
3
5
4
10
8
13
11
![Page 23: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/23.jpg)
Un altro problema correlato: l’analisi di
sensitività degli archi di un MST
Input grafo G=(V,E) pesato non orientato T=(V,ET) minimo albero ricoprente di G
Domanda quanto possono aumentare i pesi w(e) (e
E) prima di inficiare la minimalità di T?
![Page 24: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/24.jpg)
Esempio: arco non in T
66
2
7
1
9
3
10
4
10
8
13
11
![Page 25: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/25.jpg)
Esempio: arco in T
86
2
7
1
9
3
10
4
10
8
13
11
![Page 26: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/26.jpg)
Sulla complessità dei problemi
Verifica analisi disensitività
calcoloMST
riduce linearmente riduce linearmente
O(m)(m) eO(m (m,n))O(m log(m,n))
![Page 27: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/27.jpg)
Notazioni
G=(V,E), T albero ricoprente di G. Definiamo:
Per ogni f=(x,y) E\E(T) T(f): (unico) cammino semplice in T che
unisce x e y Per ogni e E(T)
C(e)={f E\E(T): e T(f)}
![Page 28: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/28.jpg)
Dim (per assurdo): Sia e l’arco più pesante in un ciclo C={e }P, e supponiamo e T
e e’ T
T’=T \ {e} {e’}
w(e’) < w(e) w(T’) < w(T)
T non è MST(G)
X
V\X
P
Proprietà dei cicliTeorema: Sia G=(V,E) un grafo non orientato e pesato, sia e l’arco più pesante di un qualsiasi ciclo in G. Allora e MST(G)
![Page 29: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/29.jpg)
Proprietà dei tagli
G=(V,E) grafo non orientato e pesatoX V un qualsiasi sottoinsieme di
verticie arco più leggero che attraversa il
taglio (X,V\X), allora
e MST(G)
![Page 30: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/30.jpg)
DimSia e l’arco più leggero del taglio (X,V\X). Sia
T=MST(G), e supponiamo e T, facciamo vedere che T MST(G)
e
e’
e : arco più leggero del taglio
w(e) < w(e’) w(T’) < w(T)T(e)
T(e): cammino in T che uniscegli estremi di eT’=T \ {e’} {e}
T non è MST(G)
X V\X
![Page 31: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/31.jpg)
Condizione di minimalità di un MST
Corollario G=(V,E) grafo non diretto, connesso,
pesato T albero ricoprente di G. allora T è minimo se e soltanto se per ogni arco
f non dell’albero vale: w(f) w(e) per ogni e in T(f)
![Page 32: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/32.jpg)
…quindi…
Se f è un arco non dell’albero T rimane minimo finché w(f) non scende
sotto w(e), dove e è l’arco più pesante in T(f); chiamiamo tale valore down(f)
Se e è un arco dell’albero T rimane minimo finché w(e) non cresce
oltre w(f), dove f è l’arco più leggero tale che e T(f) (f è chiamato arco di swap per e); chiamiamo tale valore up(e)
![Page 33: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/33.jpg)
…più formalmente…
Fare analisi di sensitività vuol dire calcolare:
Per ogni f E\E(T): down(f )= maxe T(f) w(e)
Per ogni e E(T) up(e)= minf C(e) w(f) swap(e)= arg minf C(e) w(f)
![Page 34: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/34.jpg)
Analisi di sensitività
down(f)=66
2
7
1
9
3
10
4
10
8
13
11
f
T(f)
![Page 35: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/35.jpg)
Analisi di sensitività degli archi del MST
up(e)=86
2
7
1
9
3
10
4
10
8
13
11
e
C(e)
![Page 36: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/36.jpg)
Osservazione
Calcolare tutti i valori up(e) è equivalente a calcolare il peso di un MST di G-e per ogni e di T; infatti
w(TG-e)=w(T)-w(e)+up(e)
Nel meccanismo VCG il pagamento pe di un arco e della soluzione è esattamente pari ad up(e)!!
![Page 37: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/37.jpg)
Idea dell’algoritmo efficiente
Per ogni e E(T) guardare efficientemente tutti gli archi che formano un ciclo con e e prendere il minimo (up(e))
Per ogni f E\E(T) guardare efficientemente tutti gli archi in T(f) e prendere il massimo (down(e))
![Page 38: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/38.jpg)
Il Transmuter Dato G=(V,E) e un suo albero ricoprente T, un
transmuter è un grafo diretto aciclico D che rappresenta in modo compatto l’insieme dei cicli fondamentali di G rispetto a T, ovvero l’insieme {T(f) : f arco non dell’albero}
D conterrà:1. Una sorgente (nodo con grado entrante nullo) s(e) per
ogni arco e di T2. Un pozzo (nodo con grado uscente nullo) t(f) per ogni
arco f non in T3. Un certo numero di nodi ausiliari con grado entrante pari
a 2 e grado uscente diverso da zero. Proprietà fondamentale: c’è un cammino in D
da una data sorgente s(e) a un pozzo t(f) se e solo se e T(f)
![Page 39: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/39.jpg)
Un esempio
![Page 40: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/40.jpg)
Come si costruisce un transmuter
Tarjan ha mostrato che ad ogni albero ricoprente di un grafo può essere associato un transmuter con O(m (m,n)) nodi ed archi, il quale può essere calcolato in tempo O(m (m,n))
La costruzione è un’estensione delle tecniche usate per mantenere efficientemente insiemi di foreste disgiunte sottoposte a operazioni di LINK e operazioni di EVAL
R. E. Tarjan, Application of path compression on balanced trees, J. ACM 26 (1979) pp 690-715
![Page 41: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/41.jpg)
Ordinamento topologico
D=(N,A) grafo diretto. Un ordinamento topologico di D è un ordinamento v1, v2, …,vn dei nodi tale che per ogni arco (vi, vj) A, vale i < j.
D ammette un ordinamento topologico se e solo se D è un DAG (grafo diretto aciclico).
Un ordinamento topologico dei nodi può essere trovato (se esiste) in tempo O(n+m).
![Page 42: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/42.jpg)
Calcolo degli incrementi per gli archi dell’albero
Ordiniamo topologicamente il transmuter (che è un DAG)
Etichettiamo ogni nodo del transmuter con un valore reale processando i nodi in ordine topologico inverso: Etichettiamo ogni pozzo t(f) con il valore w(f)
(associamo al valore anche l’arco f ) Etichettiamo ogni nodo v che non è un pozzo con il
valore minimo fra i valori dei suoi (immediati) successori
Quando tutti i nodi sono etichettati ogni sorgente s(e) è etichettata con il valore up(e) (e relativo arco di swap)
![Page 43: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/43.jpg)
2
5
3
6
4
9
7
8
96
11
10
7 7 6 6 9 10
7 6 10
7 8 9 6 10 11
Calcolo dei valori up(e)
![Page 44: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/44.jpg)
Calcolo dei decrementi per gli archi non dell’albero
Etichettiamo ogni nodo del transmuter con un valore reale processando i nodi in ordine topologico Etichettiamo ogni sorgente s(e) con il valore w(e)
(associamo al valore anche l’arco e) Etichettiamo ogni nodo v che non è una sorgente
con il valore massimo fra i valori dei suoi (immediati) predecessori
Quando tutti i nodi sono etichettati ogni pozzo t(f) è etichettato con il valore down(f)
![Page 45: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/45.jpg)
2
5
3
6
4
9
7
8
96
11
10
2 6 5 3 4 9
6 5 9
6 6 6 5 9 9
Calcolo dei valori down(f)
![Page 46: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/46.jpg)
Complessità temporale
1. Costruzione Transmuter: O(m (m,n))2. Calcolo valori up(e) e down(f):
Trovare l’ordinamento topologico: O(m (m,n))Processare il transmuter: O(m (m,n))
![Page 47: Il problema del minimo albero ricoprente in un grafo con archi privati](https://reader034.vdocumenti.com/reader034/viewer/2022051314/5542eb4f497959361e8be853/html5/thumbnails/47.jpg)
Complessità computazionale del VCG
TeoremaIl meccanismo VCG per il problema del MST
può essere implementato in tempo O(m (m,n)).
DimComplessità di g(٠): O(m (m,n))Complessità di p(٠): calcolo tutti i valori up(e)
in tempo O(m (m,n)).