Maurizio Patrignani
seminario sull’articolo
On the Single-Source
Unsplittable Flow Problem
di
Yefim Dinitz
Naveen Garg
Michel X. Goemans
(aprile ‘98)
grafo diretto
con capacità sugli archi
grafo diretto G(V,E)
capacità degli archi
c : E  R+
2.1
3.5
1.0
2.6
3.2
1.5
2.6
1.7
3.4
2.9
2.2
2.1
2.3
1.0
il grafo si può assumere aciclico
flow
single source - multicommodity
singola sorgente s
k terminali ti con demands di  R+
un vertice può contenere un numero arbitrario
di terminali
t1
t2
t3
s
t4
t5
t6
flow
unsplittable - fractional
unsplittable: si richiede che ogni commodity
segua un solo path dalla sorgente al
rispettivo terminale
fractional: il valore del flusso su un arco è un
numero reale
f : E  R+  0
1.2
0.9
4.1
3.1
s
6.5 1.0
2.6
3.2 1.1
1.5
2.6
1.7
3.4
2.9
2.2
2.1
2.1
2.3
2.2
1.5
quattro diversi problemi
feasibility: esiste un flusso (fractional,
unsplittable) che soddisfa tutte le
richieste senza violare i vincoli sulle
capacità degli archi?
congestion: qual’è il più piccolo valore ,
tale che moltiplicando tutte le capacità
per , il problema ha una soluzione?
number of rounds: quante tornate sono
necessarie per soddisfare tutte le
richieste?
maximization: trovare un sottoinsieme T
dei terminali per il quale il problema è
risolvibile e che massimizza  iT di
riduzione
dal partition alla feasibility
PARTITION
FEASIBILITY
2C
C
1.2
2.1
0.9
3.1
s
C
C
feasibility: esiste una soluzione
1.5
riduzione
dal partition al congestion
PARTITION
CONGESTION
1.2
2.1
0.9
s
3.1
1.5
1
1
congestion:  è il più piccolo fattore,
moltiplicando le capacità per il quale,
esiste una soluzione (confronto  con C)
riduzione
numero di rounds e massimizzazione
PARTITION
Nº OF ROUNDS
PARTITION
MAXIMIZATION
1.2
2.1
0.9
3.1
1.5
s
C
number of rounds: n rounds sono
sufficienti per soddisfare in maniera
unsplittable le richieste (confronto n con 2)
maximization: posso soddisfare in
maniera unsplittable una quantità di
richieste complessivamente pari a T
(confronto T con C)
esempio di applicazione
scheduling su una macchina parallela
macchine
lavori
p1
T
p2
T
p3
T
p4
T
p5
pn
idea base dell’articolo
parto da un flusso (non
unsplittable, frazionario) che
soddisfi tutte le richieste
lo trasformo in un flusso
unsplittable che vìola i
vincoli sulle capacità (trovo
quindi una soluzione non
ammissibile) di una quantità
che nel caso peggiore è pari
alla richiesta massima dmax
cut condition
esiste una soluzione frazionaria al
problema del multicommodity flow
non unsplittable, con capacità sugli
archi, se e solo se la seguente
condizione è verificata:
per ogni insieme di vertici S (che
non includa la sorgente) la
richiesta totale dei terminali in S
vale al massimo la capacità totale
degli archi entranti in S
s
t2
t1
t3
t6
t4
t5
t
fase di semplificazione preliminare
se f  d
d
f
d
f-d
• quando un arco raggiunge un valore
del flusso pari a zero viene rimosso
• quando un terminale raggiunge la
sorgente viene rimosso
• quando un vertice rimane sconnesso
viene rimosso
raggiungo uno
stato in cui tutti
f1
i terminali
d
residui sono
f2
“regolari”
terminale regolare  i
fi < d
schema generale dell’algoritmo
fase di semplificazione
preliminare
ricerca ciclo alternante
“travaso” di flusso
contrazione
no
è rimasta solo
la sorgente?
si
fine
invariante
piuttosto che imporre la regolarità di
tutti i terminali, nel seguito si farà
riferimento ad una condizione meno
vincolante:
d1
d2
f2
f1
invariante: ogni vertice contenente
terminali ne ha almeno uno regolare e
ha almeno due archi entranti
ricerca del ciclo alternante
vertice scelto casualmente
arco uscente scelto
casualmente
forward path
vado avanti quanto posso
(il grafo è aciclico!)
privo di
archi
uscenti
arco entrante scelto
casualmente
vado indietro fino
a che devo (fino a che incontro vertici che
hanno solamente archi entranti). Quando
incontro un arco
uscente inizio
un nuovo
forward path
chiusura del ciclo alternante
mi fermo non appena raggiungo un vertice già
incontrato
sicuramente un terminale qui
può accadere che
• un forward path intersechi un altro forward path
• un forward path intersechi un backward path
• un backward path intersechi un forward path
“travaso” del flusso
decremento il flusso sui forward path e lo
incremento sui backward path della stessa
quantità
questo “travaso” conserva il bilancio del
flusso entrante ed uscente di ogni vertice
di quanto decremento-incremento?
finché non si verifica una di queste due
condizioni:
condizione (1)
“asciugo” il flusso su un forward edge
“travaso” del flusso
condizione (2)
rendo irregolare un terminale regolare
chiamo forzanti gli archi appartenuti ad un
backward path in almeno una iterazione
(anche se non hanno mai fatto parte di un
ciclo alternante)
contrazione
ritiro un terminale t lungo un arco e se:
1) e è forzante ed f(e) = d
2) e non è forzante ed f(e)  d
risultato fondamentale
l’algoritmo trova un flusso unsplittable
tale che il flusso totale attraverso ciascun
arco eccede la sua capacità (in effetti il suo
flusso iniziale) di una quantità minore
della richiesta massima
prima di diventare forzante
attraverso l’arco possono essere
trasferiti terminali per un valore pari al
flusso sull’arco stesso
dopo essere diventato forzante
attraverso l’arco verrà trasferito al
massimo un terminale (e questo
provocherà la cancellazione dell’arco)
corollario
la somma dei flussi di tutti i terminali,
eccetto al più uno, su uno stesso arco e è
minore del flusso iniziale su e
tightness
M-M/q
M
s
M
M-M/q
M
M
M
M-M/q
M
M
M-M/q
M
M
in questa rete un flusso unsplittable, vìola
necessariamente la capacità su qualche arco
di M-M/q
al crescere di q la quantità M/q tende a zero
running time
m = |E|
n = |V|
k = nº term.
fase di semplificazione
preliminare
ricerca ciclo alternante
O(n)
“travaso” di flusso
O(k)
O(m)
contrazione
no
O(kn)
complessivi
è rimasta solo
la sorgente?
rimuove
almeno un arco
si
fine
O(nm + km)
correttezza
proprietà 3.4: se e = (u,v) è un arco forzante,
c’è al massimo un arco che esce da v ed è
anch’esso forzante
proprietà 3.5: se un vertice v ha degli archi
uscenti  tutti i suoi terminali sono regolari
se un vertice v non ha archi uscenti  ha al
massimo un terminale irregolare
invariante: ogni vertice contenente terminali
ha almeno un terminale regolare e almeno
due archi entranti
lemma 3.8: finché tutti i terminali non hanno
raggiunto la sorgente, l’algoritmo trova cicli
alternanti
proprietà 3.4
se e = (u,v) è un arco forzante, c’è al
massimo un arco che esce da v ed è
anch’esso forzante
u
e
v
nell’iterazione nella quale l’arco è diventato
forzante, ciò è vero per come ho costruito il
cliclo alternante
nessun nuovo arco viene aggiunto durante
le iterazioni successive (gli archi vengono
solo tolti)
per rimozione la proprietà non può essere
violata
proprietà 3.5
se un vertice v ha degli archi uscenti 
tutti i suoi terminali sono regolari
se un vertice v non ha archi uscenti 
ha al massimo un terminale irregolare
dimostrazione per induzione
passo base: dopo la fase di semplificazione
preliminare la proprietà è certamente
soddisfatta
passo induttivo: suppongo che la proprietà
sia soddisfatta all’iterazione i e considero
l’iterazione successiva
la proprietà non può essere violata dal
decremento di flusso di un arco entrante o
dall’uscita di un terminale da v
supponiamo che un terminale sia portato in v
proprietà 3.5 (continua)
d
v
f-d
se v aveva
più di un
arco uscente
non possono essere forzanti
per la proprietà precedente
d
v
se v aveva
un solo arco
uscente
nessuno forzante? caso precedente
d
v
al massimo
un terminale
può essere
portato in v
v aveva solo terminali regolari (ipotesi
induttiva) ora ne può avere uno irregolare (ma
non ha più archi uscenti)
invariante
ogni vertice contenente terminali ha
almeno un terminale regolare e
almeno due archi entranti
se un vertice ha archi uscenti allora tutti i
suoi terminali sono regolari (proprietà 3.5)
se ha più di un terminale allora almeno uno è
regolare (sempre per la proprietà 3.5)
rimane il caso in cui il vertice non ha archi
uscenti e ha un solo terminale
se avesse un solo arco entrante avrei mosso
il terminale lungo quell’arco
lemma 3.8
finché tutti i terminali non hanno
raggiunto la sorgente, l’algoritmo
trova cicli alternanti
nel costruire il forward path mi fermo su un
vertice che non ha archi uscenti  (buon
senso) ha terminali  (invariante) ha almeno
due archi entranti
se arrivo alla sorgente
senza trovare un arco
forward, da dove viene
questo ramo?
s
minimizzazione della congestione
nel caso in cui la capacità minima (cmin) sia
maggiore o uguale alla domanda massima
(dmax), l’algoritmo visto trova un flusso di
congestione al massimo 2
se la cut condition non è soddisfatta
1) trovo (binary search) il valore   1,
moltiplicando per il quale le capacità, la cut
condition è verificata
2) applico il metodo descritto e trovo un
flusso (unsplittable) tale che:
f(e)  c(e) + dmax
3) considero che:
c(e) + dmax  (+1)c(e)  2c(e)
siccome la congestione ottima (unsplittable
flow) non può essere minore di  (splittable
flow) se ne deduce che il mio algoritmo mi
fornisce una soluzione 2 approssimata
minimizzazione del
numero delle tornate
primo lemma
tutte le richieste minori o uguali a (1-1/q)cmin
possono essere soddisfatte in q tornate
S
T1
Tk
tutte le capacità pari a c(e)/q
dimostrazione
del lemma precedente
una soluzione trovata con il metodo
descritto precedentemente vìola la capacità
c(e)/q di un arco e di una quantità inferiore
a dmax ,cioè (1-1/q)cmin
f(e)  c(e)/q + (1-1/q)cmin 
c(e)/q + (1-1/q)c(e) = c(e)
solo una copia del grafo originale è
interessata dal routing di un terminale
ergo in q tornate soddisfo tutte le richieste
minori o uguali a (1-1/q)cmin
minimizzazione del
numero delle tornate
secondo lemma
tutte le richieste nel range [d/(q-1), d] possono
essere soddisfatte in q tornate, dove 0  d 
dmax
stessa costruzione del lemma precedente
se
c(e)  dq/(q-1) 
f(e)  c(e)/q + d 
c(e)/q + c(e)(q-1)/q = c(e)
altrimenti se c(e) < dq/(q-1)  la capacità
nelle copie del grafo è c(e)/q, cioè è minore di
d/(q-1)
al massimo un terminale è raggiunto tramite
questa copia di e nel flusso unsplittable  il
suo flusso f(e) è al massimo
d  dmax  cmin  c(e)
minimizzazione del
numero delle tornate
teorema finale
se dmax  cmin (e la cut condition è soddisfatta),
allora c’è un algoritmo polinomiale che
soddisfa tutte le richieste in 5 tornate
combinazione del primo lemma con q=2 e del
secondo lemma con q=3
con 2 tornate soddisfo tutti i terminali che
hanno una richiesta minore o uguale a
(1-1/2)cmin = 0.5 cmin
con 3 tornate soddisfo tutti i terminali che
hanno una richiesta nel range
[dmax/(3-1), dmax] = [0.5 dmax, dmax]
complessità dell’algoritmo
per la minimizzazione del numero
delle tornate
l’algoritmo base ha complessità O(nm + km)
per entrambe le reti la complessità è
O(qm qn + qkm) = O(q2 mn + q km)
quindi:
O(4mn + 2km) + O(9mn + 3km)
la complessità asintotica rimane:
O(mn + km)
minimizzazione del numero delle
tornate in assenza di cut condition
1) trovo (binary search) il valore   1,
moltiplicando per il quale le capacità, la cut
condition è verificata
il numero minimo di tornate deve essere
almeno  perché sovrapponendo n tornate
ho una congestione al più n
2) costruisco due reti: una con un numero di
copie pari a q´ = 2  e l’altra con un
numero di copie pari a q´´= 3 
3) soddisfo i terminali con richieste:
da 0 a [1-1/( 2 )] cmin
in 2  tornate
da cmin /(3  -1) fino a dmax
in 3  tornate
4) quindi soddisfo i teminali 5 