Algoritmi e Strutture Dati
Algoritmi di Approssimazione
Giuseppe Persiano
Dipartimento di Informatica ed Appl. Renato M. Capocelli
Università di Salerno
Indice
Capitolo 1. Algoritmi di Approssimazione
1. Problemi di Ottimizzazione
2. Vertex cover
3. MaxCut
4. Set cover
5. TSP
6. MaxSAT
7. Vertex Cover pesato
8. Zaino 0/1
9. Minimo makespan
10. Primale Duale
11. Esercizi
5
5
6
8
9
9
9
12
13
15
18
18
Capitolo 2. Algoritmi On-Line
1. Il problema dello sciatore
2. Ritrovare l’auto
3. Gestione online di liste
21
21
22
22
Bibliografia
25
3
4
INDICE
Sommario1
Questo documento contiene note per il secondo corso di Algoritmi e Strutture Dati che
l’autore tiene presso la Facoltà di Scienze dell’Università di Salerno.
La versione aggiornata di questo documento si trova http://libeccio.dia.unisa.it/ASDnote/apx.pdf.
1
Piacere! Mi chiamo Francesco.
CAPITOLO 1
Algoritmi di Approssimazione
1. Problemi di Ottimizzazione
Iniziamo con il definire un problema di approssimazione.
Definizione 1.1. Un problema di ottimizzazione Π è una quadrupla Π = (I, S, µ, Goal)
where
(1) I è un insieme di istanze;
(2) per ogni istanza I, S(I) è l’insieme delle soluzioni ammissibili per I;
(3) per ogni soluzione ammissibile S dell’istanza I, µ(I, S) è la misura della soluzione S.
(4) Goal∈ {min,MAX}.
Definiamo inoltre, per un’istanza I, Opt(I) nel modo seguente
Opt(I) = GoalS∈S(I) µ(I, S).
Se Goal=min diciamo che Π è un problema di minimizzazione e la misura µ di una soluzione
ammissible S è anche chiamata costo di S ed indicato con cost(I, S). Se invece Goal=MAX
diciamo che Π è un problema di massimizzazione e la misura µ di una soluzione ammissible S
è anche chiamata valore di S ed è indicato con val(I, S).
Diciamo che un algoritmo A risolve un problema di ottimizzazione Π se, per ogni istanza
I di Π, A(I) è una soluzione ammissibile per I ed inoltre
µ(I, A(I)) = Opt(I).
In queste note studieremo algoritmi che approssimano problemi di ottimizzazione nel senso che
danno in output soluzioni ammissibili la cui misura non si discosta troppo da Opt.
Definizione 1.2 (Min). Sia Π un problema di minimizazzione. L’algoritmo A k-approssima
Π se per ogni istanza I di Π
(1) A(I) ∈ S(I);
(2) cost(I, A(I)) ≤ k · Opt(I).
Definizione 1.3 (Max). Sia Π un problema di massimizazzione. L’algoritmo A k-approssima
Π se per ogni istanza I di Π
(1) A(I) ∈ S(I);
(2) val(I, A(I)) ≥ Opt(I) .
k
1.1. Problemi di decisione e di ottimizzazione. Nella prima parte abbiamo studiato
la complessità computazionale id problemi di decisione in cui il compito dell’algoritmo è di decidere se l’input x appartiene al linguaggio L. Un problema di minimizzazione Π = (I, S, µ, min)
5
6
1. ALGORITMI DI APPROSSIMAZIONE
può essere naturalmente associato ad un problema di decisione LΠ definito nel modo seguente
LΠ = {(I, k) : ∃S ∈ S(I) tale che µ(S) ≤ k}.
Una simile definizione può essere data per problemi di massimizzazione. Il seguente teorema è
immediato.
Teorema 1.4. Sia Π un problema di ottimizzazione per cui è possibile decidere in tempo
polinomiale se una soluzione S è ammissibile per un’istanza I e la funzione µ è calcolabile in
tempo polinomiale. Allora LΠ ∈ NP.
In queste note studieremo algoritmi di approssimazione per problemi di ottimizzazione Π
il cui associato linguaggio LΠ è NP − COMPLETE. Abbiamo il seguente teorema.
Teorema 1.5. Sia Π un problema di ottimizzazione per cui LΠ ∈ NP − COMPLETE e per
cui esiste un algoritmo polinomiale che risolve Π. Allora P = NP.
2. Vertex cover
In questo capitolo analiziamo la performance di alcuni algoritmi per il problema del vertex
cover. Come vedremo nessuno di questi algoritmi riesce ad approssimare il problema del vertex
cover a meno di 2. Un algoritmo che ottiene esattamente 2 può essere trovato in [1].
2.1. Definizione del problema. Il problema di ottimizzazione Vertex Cover è cosi definito.
Istanze: Un’istanza del problema del vertex cover è costituita da un grafo non diretto
G = (V, E).
Soluzioni Ammissibili: Un soluzione ammissibile per G = (V, E) è un sottoinsieme
C ⊆ V dei vertici tali che per ogni arco (u, v) ∈ E abbiamo che u ∈ C oppure v ∈ C.
Misura di una soluzione ammissibile.: La misura di una soluzione ammissibile C è
la sua cardinalità |C|.
Goal: Minimizzare.
In altre parole il problema di ottimizzazione del vertex cover consiste nel coprire tutti gli archi
di G usando il minor numero possibile di vertici.
2.2. Un algoritmo 2 approssimato. Vedi [1].
2.3. Algoritmo greedy. Consideriamo il seguente algoritmo.
Greedy(G)
01. A ← ∅;
02. while E 6= ∅ do
03.
Scegli arbitrariamente un vertice v di G che ha almeno un arco;
04.
A ← A ∪ {v};
05.
E ← E \ {e ∈ E|e = (u, v) per qualche vertice u};
06. end ;
07. return A;
2. VERTEX COVER
7
È facile convincersi che l’algortimo Greedy restituisce sempre un vertex cover di G.
Mostriamo ora che esiste un grafo di n vertici ed una scelta dei vertici al passo 03. per cui
l’algoritmo Greedy calcola un vertex cover di cardinalità Ω(n) volte il vertex cover ottimo.
Consideriamo il grafo stella Sn con n vertici; l’insieme di vertici di Sn consiste dei vertici
(v, u1 , · · · , un−1 ) e Sn contiene gli archi (v, ui ) per i = 1, · · · , n − 1. Se al passo 03 sono scelti i
vertici u1 , · · · , un−1 , l’algoritmo Greedy restituisce un vertex cover di cardinalità n−1 mentre
il vertice v da solo costituisce un vertex cover.
2.4. Analisi dell’euristica del prof. Nixon. Questa sezione presenta una differente
euristica per il calcolo del vertex cover. L’euristica è attribuita (scherzosamente) a tale professor
Nixon da [1]. Risponderemo ad un quesito di [1] che chiede un esempio in cui l’euristica
di Nixon costruisce un vertex cover di taglia maggiore del doppio del vertex cover ottimo.
Mostreremo poi un altro esempio in cui l’euristica del professor Nixon restituisce un vertex
cover di taglia Ω(log n) volte il vertex cover ottimo.
Il professor Nixon propone la seguente euristica per approssimare il problem del vertex
cover su un grafo G = (V, E).
Nixon(G = (V, E))
1. A = ∅;
2. while E 6= ∅
3.
sia u vertice di grado massimo in (V, E);
4.
E ← E \ {archi incidenti a u};
5.
V = V \ {u};
6.
A = A ∪ {u};
7. endwhile;
8. return A;
Primo controesempio. Mostreremo ora un grafo G su cui l’algoritmo Nixon restituisce
un vertex cover di taglia maggiore del doppio dell’ottimo. Quindi l’algoritmo Nixon ha una
garanzia di approssimazione peggiore dell’algoritmo presentato a lezione.
Il grafo G = (V1 ∪ V2 , E) è un grafo bipartito. L’insieme V1 consiste di 8 vertici v1 , · · · , v8
di grado 6. L’insieme V2 è l’unione (disgiunta) di 4 insiemi: A, B, C e D. L’insieme A consiste
di 3 vertici a1 , a2 , a3 di grado 8, l’insieme B consiste di 2 vertici b1 , b2 di grado 4, l’insieme C
consiste di 4 vertici c1 , c2 , c3 , c4 di grado 2, l’insieme D consiste di 8 vertici d1 , · · · , d8 di grado
1.
Gli archi di G sono come segue:
(1) ogni vertice di V1 ha un arco ad ogni vertice di A;
(2) vertici v1 , · · · , v4 hanno ciascuno un arco incidente a b1 ; vertici v5 , · · · , v8 invece hanno
ciascuno un arco incidente a b2 ;
(3) vertici v1 e v2 hanno un arco a c1 ; vertici v3 e v4 hanno un arco a c2 ; vertici v5 e v6
hanno un arco a c3 ; vertici v7 e v8 hanno un arco a c4 .
(4) per i = 1, · · · , 8 il vertice vi ha una arco a di .
L’algoritmo Nixon sceglie i vertici nel modo seguente.
(1) i 3 vertici di A che hanno grado 8 mentre gli atri vertici hanno tutti grado al più 6.
Dopo l’eliminazione dei vertici di A, i vertici di V1 hanno grado 6 − 3 = 3;
8
1. ALGORITMI DI APPROSSIMAZIONE
(2) i 2 vertici di B che hanno grado 4 mentre tutti gli altri hanno grado al più 3. Dopo
l’eliminazione dei vertici di B, i vertici di V1 hanno grado 2;
(3) i 4 vertici di C che hanno grado 2. Tutti gli altri vertici ancora presenti nel grafo
hanno o grado 2 (i vertici di V1 ) o grado 1 (i vertici di D);
(4) a questo punto il grafo consiste di 8 coppie di vertici di grado 1; l’algoritmo per
terminare ne sceglie 8;
Quindi l’algoritmo Nixon restituisce un vertex cover di cardinalità 17. È facile convincersi che
gli 8 vertici di V1 costituiscono un vertex cover.
Secondo controesempio. Consideriamo il grafo bipartito B(L, R, E). L’insieme L consiste
di r vertici. L’insieme R è suddiviso in r insiemi R1 , · · · , Rr . Ogni vertice in Ri ha un arco
verso i vertici di L e due vertici di Ri non hanno archi verso lo stesso vertice di L. Pertanto
l’insieme Ri contiene br/ic vertici. L’insieme R ha quindi
r
X
i=1
br/ic = Θ(r log r)
vertici. Il numero di vertice n è Θ(r log r).
Se l’algoritmo Greedy considera i vertici di R a partire dai vertici di Rr fino a i vertici di
R1 , il cover calcolato coincide con R ed ha cardinalità Θ(r log r). Osserviamo invece che L è
un cover ed ha cardinalità r. Quindi |R|/|L| = Ω(log r) = Ω(log n).
3. MaxCut
Il problema MaxCut è definito come segue.
Istanze: Un’istanza del problema MaxCut è costituita da un grafo non diretto G =
(V, E).
Soluzioni Ammissibili: Un soluzione ammissibile per G = (V, E) è una partizione di
V in due sottoinsiemi S1 e S2 tali che S1 ∪ S2 = V e S1 ∩ S2 = ∅.
Misura di una soluzione ammissibile: La misura di una soluzione ammissibile c(S1 , S2 )
è il numero di archi che hanno un estremo in S1 e l’altro in S2 .
Goal: Massimizzare.
Osserviamo che il problema di minimizzazione è risolvibile in tempo polinomiale.
L’algoritmo che presentiamo consiste nel partire da una qualsiasi partizione S 1 ed S2 e
controllare se esiste un vertice x ∈ S1 tale che c(S1 \ {x}, S2 ∪ {x}) > c(S1 , S2 ) nel qual caso
si aggiorna la soluzione corrente a (S1 \ {x}, S2 ∪ {x}) oppure se esiste un vertice x ∈ S2
tale che c(S1 ∪ {x}, S2 \ {x}) > c(S1 , S2 ). nel qual caso si aggiorna la soluzione corrente a
(S1 ∪ {x}, S2 \ {x}). Se invece nessun vertice esiste x l’algoritmo si ferma e dà in output la
soluzione corrente (S1 , S2 ).
Abbiamo il seguente teorema.
Teorema 1.6. Esiste un algoritmo polinomiale che 2-approssima MaxCut.
Dimostrazione. Osserviamo che per ogni (S1 , S2 ) abbiamo che c(S1 , S2 ) ≤ |E| e poiché
ad ogni iterazione il valore di c(S1 , S2 ) è incrementato di almeno 1 l’algoritmo effettua al più
|E| iterazioni ed è pertanto polinomiale.
6. MaxSAT
9
Osserviamo che nella soluzione data in output dall’algoritmo per ogni vertice x almeno
metà dei suoi vicini appartengono all’altro sottoinsieme. Pertanto, se denotiamo con d x il
grado del vertice x, abbiamo che
X dx
2 · c(S1 , S2 ) ≥
2
x
= |E|
Il teorema segue dall’osservazione che Opt ≤ |E|.
4. Set cover
Vedi [1].
5. TSP
5.1. Definizione. Vedi [1].
5.2. Approssimabilità del caso generale. Vedi [1].
5.3. Algoritmo 2 approssimato per il caso euclideo. Vedi [1].
5.4. Algoritmo 3/2 approssimato per il caso euclideo.
6. MaxSAT
In questo capitolo discutiamo algoritmi di approssimazione per MaxSat. L’esposizione è
basata su [2].
6.1. Ripasso di calcolo delle probabilità. Useremo la seguente proprietà della media
di una variabile casuale
(1) Se E[X] ≥ µ allora esiste almeno un risultato r tale che X(r) ≥ µ.
6.2. Definizione. Il problema MaxSAT consiste nel calcolare, avendo in input una formula Φ in forma congiuntiva normale Φ = C1 ∧ · · · ∧ Cm sulle variabili x1 , · · · , xn , il numero
massimo di clausole che possono essere simultaneamente soddisfatte da un assegnamento di
verità. Ovviamente se esiste un algoritmo che risolve MaxSAT allora P=NP.
6.3. Esiste sempre un assegnamento buono. Supponiamo di scegliere un assegnamento casuale assegnando alla variabile xi il valore VERO con probabilità 1/2. È facile vedere
def
che la probabilità che una clausola con k letterali sia soddisfatta è α k = 1 − 2−k . Definiamo
quindi la variabile casuale X Φ come la variabile casuale che conta il numero di clausole di Φ soddisfatte da un assegnamento casuale. Definiamo inoltre la variabile casuale X iΦ , i = 1, · · · , m,
nel modo seguente
(
1, se Ci soddisfatta;
XiΦ =
0, altrimenti;
10
1. ALGORITMI DI APPROSSIMAZIONE
ed abbiamo che E[XiΦ ] = αk . Quindi il numero medio E(X Φ ) di clausole di Φ soddisfatte da
un assegnamento casuale è dato da
"m
#
X
X
Φ
E
Xi =
αl m l
i=1
l
ove ml denota il numero di clausole con l letterali. Poichè αl ≥ 1/2 possiamo concludere che il
numero medio di clausole soddisfatte è almeno m/2 e quindi, per la proprietà della media nel
Paragrafo 6.1, esiste sempre un assegnamento di verità che soddisfa almeno metà delle clausole.
Notiamo che la qualità dell’approssimazione cresce con il numero di letterali che compaiono
in una clausola. Se ogni clausola ha almeno due letterali abbiamo che per l ≥ 2, α l ≥ 3/4 e
possiamo quindi concludere che esiste sempre un assegnamento che soddisfa almeno 3/4 delle
clausole. Se tutte le clausole invece hanno almeno 3 letterali allora possiamo concludere che
esiste almemo un assegnamento che soddisfa almeno 7/8 delle clausole.
6.4. Cerchiamo un assegnamento buono. In questa sezione mostriamo come riusciamo a trovare un assegnamento che soddisfi almeno 1/2m delle m clausole della formula Φ.
Poiché l’assegnamento che soddisfa il maggior numero di clausole non ne soddisfa più di m,
abbiamo un algoritmo che 1/2-approssima MaxSAT.
Calcoliamo un assegnamento una variabile per volta partendo da x1 usando il metodo
delle medie condizionate. Consideriamo le formule Φ(x1 = 1) e Φ(x1 = 0) ottenendo ponendo
x1 = 1 e x1 = 0 nella formula Φ. Assegnamo quindi alla variabile x1 il valore b che massimizza
E(X Φ |x1 = b). Osserviamo che siccome E(X Φ ) = 12 (E(X Φ |x1 = 1) + E(X Φ |x1 = 0) e poiché
E(X Φ ) ≥ 1/2 abbiamo che E(X Φ |x1 = b) ≥ 1/2. Il valore di x2 è determinato allo stesso
modo considerando la formula Φ(x1 = b) invece che la formula Φ e cosı̀ via.
Abbiamo quindi il seguente teorema.
Teorema 1.7. Esiste un algoritmo polinomiale che 1/2 approssima MaxSAT.
6.5. Programmazione lineare. MaxSAT può essere formulato come il seguente problema di programmazione lineare intera.
P
max W = m
j=1 zj
con vincoli
P
P
j = 1, · · · , m
i∈I + yi +
i∈I − (1 − yi ) ≥ zj
j
yi ∈ {0, 1}
0 ≤ zj ≤ 1
j
i = 1, · · · , n
j = 1, · · · , m
dove abbiamo indicato con Ij+ l’insieme delle variabili che compaiono in forma non negata nella
clausola Cj e con Ij− le variabili che compaiono in forma negata. Per ogni assegnamento di
verità (x1 , · · · , xn ) alle variabili della formula Φ il problema ha come valore massimo il numero
delle clausole soddisfatte. Infatti la soluzione che assegna a yi il valore di verità della varibaile
xi e a zj assegna 1 se la j-esima clausola è soddisfatta e 0 altrimenti è ammissibile ed ottima.
Denotiamo con ZI∗ il valore del problema intero e con ZL∗ il valore del problema che si
ottiene rilassando il vincolo di interezza sulle variabili yi . Ovviamente, ZL? ≥ ZI? = Opt.
Consideriamo quindi il seguente semplice algoritmo
Passo 1.: Risolvere il problema rilassato ottendo soluzione (y ? , z ? ).
6. MaxSAT
11
Passo 2.: Applicare il metodo della sezione precedente usando yi∗ come probabilità di
porre a VERO la variabile xi .
Lemma 1.8. Se per una la soluzione ottima (y ∗ , z ∗ ) al problema lineare rilassato vale che
per ogni clausola Cj
1 − Πi∈I + (1 − yi? ) · Πi∈I − yi? ≥ αzj?
j
j
allora
E[X Φ ] ≥ αZI? .
P
Dimostrazione. Abbiamo che E[X Φ ] = m
j=1 Pr(zj = 1). La variabile zj ha valore 0 se
e solo se tutte le varibaili che compaiono nella j-esima clausola in forma non negata hanno
valore falso (evento con probabilità Πi∈I + (1 − yi? )) e tutti le variabile che compaiono in forma
j
negata hanno valore vero (evento con probabilità Πi∈I − yi? ). Pertanto abbiamo che
j
Φ
E[X ] =
m X
j=1
Πi∈I + (1 −
j
yi? )
·
Πi∈I − yi?
j
≥
m
X
j=1
αzj∗ = αZL? ≥ αZI? .
Quindi se l’ipotesi del teorema è soddisfatta l’algoritmo descritto garantisce una α-approssimazione.
Per il prossimo lemma usiamo la seguente ben nota diseguaglianza tra la media geometrica e
la media aritmentica di una sequenza (a1 , · · · , ak ) di numeri non negativi
√
a1 + a 2 + · · · + a k
≥ k a1 · · · ak .
k
Lemma 1.9. Per ogni soluzione ammissibile (y, z) del problema lineare rilassato e per ogni
clausola Cj con k letterali abbiamo
1 − Πi∈I + (1 − yi ) · Πi∈I − yi ≥ βk zj
j
con
j
1
βk = 1 − 1 −
k
k
.
Dimostrazione. Supponiamo che la clausola Cj contenga solo letterali in forma non negata. Se xi appare in forma negata in Cj allora basta sostituire xi con x̄i e viceversa in tutte le
clausole della formula e yi con 1−yi ed ottenere una formula ed un problema lineare equivalenti.
Inoltre possiamo assumere che la clausola Cj contenga le variabile x1 , · · · , xk .
P
Se (y, z) è una soluzione ammissibile allora il problema lineare comprende il vincolo ki=1 yi ≥
zj . Quindi
!k
Pk
k
i=1 (1 − yi )
1 − Πi=1 (1 − yi ) ≥ 1 −
k
!k
Pk
i=1 yi
= 1− 1−
k
zj k
≥ 1− 1−
.
k
12
1. ALGORITMI DI APPROSSIMAZIONE
Osserviamo ora che la funzione
zj k
f (zj ) = 1 − 1 −
k
è concava e poichè f (0) = 0 e f (1) = βk abbiamo che, per ogni 0 ≤ zj ≤ 1, f (zj ) ≥ βk zj .
Abbiamo quindi il seguente teorema.
Teorema 1.10. Esiste un algoritmo che 1 −
1
e
≈ .63099... approssima MaxSAT.
Dimostrazione. Per il Lemma 1.8 e il Lemma 1.9 abbiamo che se la formula contiene clausole ciascuna con almeno k letterali allora esiste un assegnamento che soddisfa almeno β k Opt
clausole. Poiché per ogni k abbiamo che βk < 1 − 1e per ogni formula esiste un assegnamento
che soddisfa almeno (1 − 1e )Opt clausole. Usando il metodo delle medie condizionate possiamo
in tempo polinomiale calcolare un assegnamento che soddisfa (1 − 1e )Opt clausole.
6.6. Un algoritmo 3/4-approssimato. Combiniamo i due algoritmi nel modo seguente.
Scegliamo b ← {0, 1} a caso. Se b = 0 eseguiamo l’algoritmo del Teorema 1.7. Se b = 1
eseguiamo l’algoritmo del Teorema 1.10.
Calcoliamo per la clausola Cj che ha kj letterali la probabilità pj che Cj sia soddisfatta.
Denotiamo con (y ? , z ? ) la soluzione ottima al problema di programmazione lineare. Sappiamo
che se b = 0 allora la probabilità che Cj sia soddisfatta è αkj ≥ αkj zj? (poiché zj? ≤ 1). Se
invece b = 1 allora la probabilità che Cj sia soddisfatta è βkj zj? . Quindi
E[X Φ ] ≥
m
X
α kj + β kj ?
zj
2
j=1
e siccome αk + βk ≥ 3/2 per ogni k abbiamo che E[X Φ ] ≥ 3/4zj? . Questo dimostra che esiste
un assegnamento che soddisfa almeno 3/4m clausole.
Consideriamo quindi il seguente algoritmo: calcoliamo assegnamenti t1 e t2 usando rispettivamente l’algoritmo 1/2 approssimato e l’algoritmo 1 − 1e approssimato. Diamo in output
l’assegnamento ta con a ∈ {1, 2} che soddisfa il maggior numero di clausole. Siccome sappiamo
che se scegliamo uno dei due assegnamenti a caso sono soddisfatte in media 3/4m clausole,
allora ta soddisfa almeno 3/4m clausole.
7. Vertex Cover pesato
Il problema del vertex cover pesato è definito nel modo seguente. Un’istanza consiste di
un grafo G = (V, E) in cui ad ogni vertice v è associato un peso w(v) > 0. Una soluzione
ammissibile è un sottoinsieme S ⊆ V dei vertici tale che perP
ogni arco (u, v) ∈ E uno tra u e
v appartiene ad S. Il costo di una soluzione S è la somma v∈S w(v) dei pesi dei vertici di
S. L’obiettivo è di minimizzare il costo. Questo problema puó essere scritto sotto forma di
problema di programmazione lineare intera nel modo seguente.
P
min v∈V x(v) · w(v)
con vincoli
x(u) + x(v) ≥ 1
∀(u, v) ∈ E
x(v) ∈ {0, 1}
∀v ∈ V
8. ZAINO 0/1
13
Denotiamo con Opt(G, w) il valore dell’ottimo del problema di programmazione lineare intera
per l’istanza (G, w) e con L(G, w) il valore del problema di programmazione lineare ottenuto
rilassando il vincolo di interezza x(v) ∈ {0, 1} al vincolo 0 ≤ x(v) ≤ 1 e sia x ? una soluzione
che ottiene L(G, w). Partendo da x? costruiamo il vettore x nel modo seguente
(
1, se x? (v) ≥ 1/2;
x(v) =
0, altrimenti;
e sia S l’insieme dei vertici v per cui x(v) = 1. Osserviamo che S è una soluzione ammissibile.
Infatti siccome x? è una soluzione ammissibile abbiamo che per ogni arco (u, v) abbiamo
x? (u) + x? (v) ≥ 1 e quindi o x? (u) ≥ 1/2 (e quindi x(u) = 1) oppure x? (v) ≥ 1/2 (e quindi
x(v) = 1).
Calcoliamo il peso di S.
X
X
x(u)w(u) ≤
2x? (u)w(u) = 2L(G, w) ≤ 2Opt(G, w).
u∈V
u∈V
Quindi abbiamo il seguente teorema.
Teorema 1.11. Esiste un algoritmo polinomiale 2-approssimante per il problema del vertex
cover pesato.
8. Zaino 0/1
Un’istanza I del problema dello zaino 0/1 è costituita da n oggetti e da una capacità massima B. L’i-esimo oggetto ha peso (volume) ci e valore (prezzo) vi . Lo scopo è di individuare
il sottoinsieme di prezzo massimo tra quelli che hanno volume complessivo non maggiore di B.
Formalmente, una soluzione ammissibile per un’istanza I = ((v1 , · · · , vn ), (c1 , · · · , cn ), B)
è costituita da una sequenza S = (b1 , · · · , bn ) ∈ {0, 1}n tale che
n
X
i=1
bi · ci ≤ B.
Il nostro compito è quello di trovare, tra tutte le soluzioni ammissibili per un’istanza I, una
soluzione S ∗ = (b∗1 , · · · , b∗n ) che massimizzi il profitto V al(S ∗ , I) di S ∗ definito come
V al(S ∗ , I) =
n
X
i=1
b∗i · vi .
8.1. Hardness dell’approssimazione. In questa sezione proviamo che, se P 6= NP, nessun algoritmo polinomiale A può risolvere il problema dello zaino garantendo un’approssimazione assoluta costante; cioè tale che per una costante k e per ogni istanza I, Opt(I) − A(I) ≤
k.
Teorema 1.12. Se P 6= NP allora per ogni costante k, nessun algoritmo polinomiale A
può risolvere il problema dello zaino garantendo Opt(I) − A(I) ≤ k.
Dimostrazione. Supponiamo per assurdo che l’algoritmo polinomiale A sia tale che, per
ogni istanza I, Opt(I) − A(I) ≤ k. Costruiamo un altro algoritmo A 0 che risolve il problema
dello zaino in tempo polinomiale, contradicendo l’ipotesi che P 6= NP.
14
1. ALGORITMI DI APPROSSIMAZIONE
L’algoritmo A0 riceve in input un istanza I = ((v1 , · · · , vn ), (c1 , · · · , cn ), B) e costruisce
l’istanza I 0 = (((k + 1)v1 , · · · , (k + 1)vn ), (c1 , · · · , cn ), B). Notiamo che, non avendo variato
i pesi ci e la capacità B dello zaino, l’insieme delle soluzioni ammissibili delle due istanze
coincidono. L’algoritmo A0 esegue l’algoritmo A sull’istanza I 0 ottenendo una soluzione S.
Notiamo che V al(S, I 0 ) = (k + 1)V al(S, I) e Opt(I 0 ) = (k + 1)Opt(I). Inoltre per ipotesi vale
che Opt(I 0 ) − V al(S, I 0 ) ≤ k. Quindi
k
Opt(I) − C(S, I) ≤
.
k+1
Poiché Opt(I) e V al(S, I) sono interi e poiché
k
k+1
< 1, abbiamo che
Opt(I) − V al(S, I) = 0
e quindi S è una soluzione ottima per I.
8.2. Algoritmo pseudopolinomiale. Data un’istanza I = ((v1 , · · · , vn ), (c1 , · · · , cn ), B)
denotiamo con C(j, v) il piú piccolo valore b per cui l’istanza ((v1 , · · · , vj ), (c1 , · · · , cj ), b) ha
valore ottimo almeno v. Abbiamo
C(j, v) = 0, v ≤ 0 e j = 0, 1, · · · , n,
C(0, v) = +∞ per v > 0,
e
C(j, v) = min{C(j − 1, v − vj ) + cj , C(j − 1, v)}.
La tabella C viene calcolata (ogni entry prende tempo O(1)) per ottenere il massimo v tale
=
P
che C(n, v) ≤ B. Poiché vale che Opt(I) ≤
vi def V ? , calcoliamo le entri di C(j, v) con
v = 0, · · · , V ? . L’algoritmo quindi prende tempo O(nV ? ). Notiamo che quindi l’algoritmo non
è polinomiale.
8.3. Uno schema di approssimazione. Data un’istanza I = ((v1 , · · · , vn ), (c1 , · · · , cn ), B)
ed un intero k consideriamo l’istanza k-scalata I 0 (k) = ((v1 (k), · · · , vn (k)), (c1 , · · · , cn ), B) dove
jv k
i
vi (k) =
.
k
Calcoliamo la soluzione ottima S 0 (k) dell’istanza I 0 (k) usando l’algoritmo della sezione precedente.
P
Il tempo d’esecuzione dell’algoritmo è O(nV 0 (k)) ove V 0 (k) =
i vi (k). D’altro canto
abbiamo V 0 (k) ≤ nVmax (k) ≤ nVmax /k, ove Vmax e Vmax (k) sono il valore massimo di un
oggetto nell’istanza originale e nell’istanza scalata. Quindi il tempo d’esecuzione dell’algoritmo
che risolve ottimamente la versione scalata del problema è O(n2 Vmax /k).
Valutiamo ora la bontà della soluzione ottenuta. Sia S 0 l’insieme di oggetti in una soluzione
ottima di I. Abbiamo
X
X j vi k
X j vi k
X vi
X
V al(S 0 (k), I) =
vi ≥ k
≥k
≥k
( −1) ≥
(vi − k) ≥ Opt(I)−k|S 0 |.
k
k
k
0
0
0
0
0
i∈S (k)
Quindi
essendo Opt(I) ≥ Vmax
i∈S (k)
i∈S
i∈S
k|S 0 |
nk
V al(S 0 (k), I)
≥1−
≥1−
Opt(I)
Opt(I)
Vmax
e |S ∗ | ≤ n.
i∈S
9. MINIMO MAKESPAN
15
In conclusione, se desideriamo che l’algoritmo approssimato restituisca una soluzione che
valga almeno (1 − ) volte l’ottimo scegliamo k nel modo seguente.
Se b Vmax
n c = 0 allora Vmax < n/ e quindi l’algoritmo della sezione precedente prende
tempo O(n2 Vmax ) = O(n3 /) e dà la soluzione ottima. Se b Vmax
n c > 0 allora poniamo k =
c.
In
questo
caso
la
soluzione
ottenuta
è
(1−)-approssimata
e l’algoritmo prende tempo
b Vmax
n
2
3
O(n Vmax /k) = O(n /).
9. Minimo makespan
Un’istanza consiste di un insieme J di n job di lunghezza p1 , · · · , pn da eseguire su m
macchine identiche. Una soluzione ammissibile consiste in uno schedule; cioè una partizione
S = hS1 , · · · , Sm i di J in m insiemi. Il costo M S(S) di uno schedule S è il suo makespan
definito come
m X
M S(S) = max
pj .
i=1
j∈Si
9.1. Algoritmo List Scheduling. Esiste un algoritmo molto semplice che approssima
il problema dello schedule con minimo makespan. L’algoritmo ListScheduling considera i
job uno per volta ed assegna ciascun job alla macchina che ha il minor carico.
ListScheduling(p1 , · · · , pn , m)
1. l1 , · · · , lm ← 0;
2. for i = 1 to n
3.
sia j tale che lj = minh {lh };
4.
S(i) = j;
5.
l j = l j + pi ;
6. end;
7. output S;
Teorema
1.13. L’algoritmo ListScheduling ottiene un rapporto di approssimazione
1
2 − m , ove m è il numero delle macchine.
Dimostrazione. Sia i l’ultimo job a terminare nello schedule prodotto dall’algoritmo
ListScheduling. Sia τ l’istante in cui il job i inizia. Abbiamo quindi che lo schedule calcolato
da ListScheduling ha lunghezza τ + pi .
Osserviamo che per il makespan ottimo vale
n
Opt(p1 , · · · , pn , m) ≥
ed inoltre che
1 X
ph
m
h=1
Opt(p1 , · · · , pn , m) ≥ pi .
Fino all’istante τ le macchine sono tutte occupate (altrimenti il job i-esimo sarebbe stato
schedulato su una macchina non occupata) ad eseguire job diversi da i e quindi abbiamo che
1 X
ph ≥ τ.
m
h6=i
16
1. ALGORITMI DI APPROSSIMAZIONE
Possiamo quindi concludere che
n
1
1 X
1 X
1
ph + 1 −
τ + pi ≤
ph + p i =
pi ≤ 2 −
Opt(p1 , · · · , pn , m).
m
m
m
m
h6=i
h=1
Mostriamo ora che esiste una sequenza di job per cui l’algoritmo ListScheduling resti1
) volte quello ottimo. Infatti, se abbiamo m(m − 1)
tuisce uno schedule che ha makespan (2 − m
job di lunghezza 1 ed 1 di lunghezza m, ListScheduling produce uno schedule con makespan
2m − 1 mentre lo schedule ottimo ha makespan m.
9.2. Job ordinati. In questa sezione studiamo l’algoritmo LongestFirst che considera
i job in ordine non decrescente di lunghezza e poi applica l’algortimo ListScheduling.
Abbiamo il seguente teorema.
Teorema 1.14. Per ogni istanza I del problema dello scheduling abbiamo che
4
1
LongestFirst(I) ≤
−
· Opt(I),
3 3m
ove m è il numero di macchine.
cui
Dimostrazione. Sia (p1 , · · · , pn ) una sequenza di job con il minimo numero di job per
(1)
LongestFirst(I) >
4
1
−
3 3m
· Opt(I).
Assumiamo che p1 ≥ p2 ≥ · · · ≥ pn .
Osserviamo che se lo schedule ottimo assegna al piú due job per macchina (e pertanto
n ≤ 2m) allora LongestFirst calcola una soluzione ottima.
Supponiamo che l’ultimo job a terminare sia pk , con k < n, e consideriamo l’istanza Ik che
consiste dei primi k job di I. Allora abbiamo che LongestFirst(Ik ) = LongestFirst(I) e
Opt(Ik ) ≤ Opt(I). Per l’ipotesi fatta abbiamo
4
4
1
1
−
−
LongestFirst(Ik ) = LongestFirst(I) >
· Opt(I) ≥
· Opt(Ik )
3 3m
3 3m
contraddicendo la minimalità di I. Pertanto abbiamo che l’ultimo job a terminare è p n .
Il job pn ha iniziato al tempo LongestFirst(I) − pn e a quell’istante tutte le macchine
sono occupate. Quindi abbiamo che
n−1
1 X
pi
LongestFirst(I) − pn ≤
m
i=1
da cui
n−1
n
1 X
1 X
m−1
LongestFirst(I) ≤ pn +
pn .
pi =
pi +
m
m
m
i=1
i=1
1 Pn
Poiché abbiamo che Opt(I) ≥ m
i=1 pi possiamo concludere che
(2)
LongestFirst(I) − Opt(I) ≤
m−1
pn .
m
9. MINIMO MAKESPAN
17
Per l’Equazione 1 abbiamo
(3)
LongestFirst(I) − Opt(I) >
m−1
Opt(I).
3m
Usando Eq. 2 ed Eq. 3, otteniamo
Opt(I) <
3m m − 1
pn < 3pn .
m−1 m
Quindi se assumiamo che esiste un’istanza I su cui LongestFirst ha una rapporto di
approssimazione peggiore di 4/3 − 1/3m allora possiamo concludere che l’ottimo su I assegna
al piú due job per macchina. Su questa classe di istanze però LongestFirst produce uno
schedule di makespan minimo. Contraddizione.
Il bound ottenuto nel teorema precedente è tight. Per ogni m, consideriamo 2m + 1 job
di lunghezza pi = 2m − b(i + 1)/2c per i = 1, 2, · · · , 2m e p2m+1 = m. I primi 2m job sono
assegnati da LongestFirst nel modo seguente: la macchina i riceve i job i e 2m − i + 1 per
un carico totale di 3m − 1. In piú ad una macchina viene assegnato il job p 2m+1 di lunghezza
m. Quindi LongestFirst ottiene un makespan 4m − 1.
L’ottimo invece è 3m e si ottiene assegnando alla macchina n i tre job piú corti (di lunghezza
m). Ciascuna delle restanti macchine invece riceve due job; piú precisamente la macchina i
riceve i job i e 2m − i − 1 per un carico totale di 3m.
9.3. Uno schema di approssimazione polinomiale. Uno schema di approssimazione
polinomiale (PTAS in breve) è una famiglia S = {S } di algoritmi. In questa sezione mostreremo, che ogni numero m fissato di macchine, un PTAS tale che l’algoritmo S ha tempo di
esecuzione polinomiale in n (numero di job) e produce uno schedule di makespan al piú (1 + )
volte l’ottimo.
Consideriamo il seguente algoritmo Ak che riceve in input le lunghezze di n job ordinate
in ordine non decrescente (cioè, p1 ≥ p2 ≥ · · · ≥ pn ) e il numero m di macchine:
Fase I.: Calcola uno schedule di makespan minimo per i primi k job.
Fase II.: Partendo dallo schedule parziale prodotto nella Fase I, utilizza ListScheduling sui rimanenti n − k job.
Abbiamo il seguente risultato.
Teorema 1.15. L’algoritmo Ak ottiene un rapporto di approssimazione minore o uguale a
1+
m−1
k
ove m è il numero delle macchine.
Dimostrazione. Lo schedule prodotto alla fine della Fase I ha makespan Opt(p 1 , · · · , pk , m)
e denotiamo, con leggero abuso di notazione, con Ak il makespan prodotto dall’algoritmo Ak .
Se Ak = Opt(p1 , · · · , pk , m) allora, poichè Opt(p1 , · · · , pk , m) ≤ Opt(p1 , · · · , pn , m), lo
schedule prodotto dall’algoritmo Ak è ottimo e il teorema vale.
Se, invece, Ak > Opt(p1 , · · · , pk , m) allora esiste un job i > k che termina al tempo Ak .
Sia τ l’istante di inizio del job i e quindi abbiamo che Ak = τ + pi . Per gli stessi argomenti
18
1. ALGORITMI DI APPROSSIMAZIONE
usati nella prova del Teorema 1.13 abbiamo che
(4)
Ak = τ + p i
n
1 X
ph + 1 −
≤
m
h=1
n
X
1
ph + 1 −
≤
m
(5)
(6)
h=1
1
m
pi
1
m
pk ,
ove l’ultima diseguaglianza
segue dal fatto che i > k e quindi pi ≤ pk . Ora abbiamo che
1 Pn
Opt(p1 , · · · , pn , m) ≥ m
h=1 ph . Inoltre, osserviamo che nello schedule ottimo per (p1 , · · · , pk , m)
k
e job ciascuno di
calcolato nella Fase I, esiste almeno una macchina che riceve almeno d m
lunghezza almeno pk . Pertanto abbiamo che
k
Opt(p1 , · · · , pn , m) ≥ Opt(p1 , · · · , pk , m) ≥
pk
m
da cui abbiamo
Opt(p1 , · · · , pn , m)
Opt(p1 , · · · , pn , m)
≤
.
k
k
dme
m
Sostituendo nell’Equazione 6 abbiamo il teorema.
pk ≤
L’algoritmo S esegue l’algoritmo Ak con k = d m
e. Per il teorema precedente Ak restituisce
una soluzione (1+)-approssimata. Calcoliamo un limite al tempo di esecuzione dell’algoritmo.
La Fase I prende tempo O(mk ) mentre Fase II prende tempo m · n per cui, essendo m ≤ n, il
m
tempo di esecuzione dell’algoritmo è O(n ) che è polinomiale in n per m fissato.
9.4. Nota bibliografica. Gli algoritmi discussi in questo capitolo sono stati presentati
per la prima volta in [3, 4]. Lo schema presentato nella Sezione 9.3 è polinomiale per un
numero fissato di macchine. In [5] è presentato uno schema che è polinomiale per un qualsiasi
numero di macchine.
10. Primale Duale
10.1. Set Cover Pesato. Vedi [6] pag. 15-17.
10.2. Primale e Duale. Vedi [6] pag. 93-97.
10.3. Primale Duale per Set Cover Pesato. Vedi [6] pag. 108-111.
11. Esercizi
Esercizio 1.1. Dimostrare il Teorema 1.4.
Esercizio 1.2. Dimostrare il Teorema 1.5.
Esercizio 1.3. Provare che il seguente algoritmo 1/2-approssima MaxSAT: sia t l’assegnamento che pone tutte le variabili a VERO e sia t̂ l’assegnamento che pone tutte le variabili
a FALSO. L’algoritmo restituisce l’assegnamento che tra t e t̂ soddisfa il maggior numero di
clausole.
11. ESERCIZI
19
Esercizio 1.4. Si consideri il seguente algoritmo per MaxCut: ogni vertice è assegnato
con probabilità 1/2 a S1 e con probabilità 1/2 a S2 . Dimostrare che il numero medio di archi
che hanno un estremo un S1 e l’altro in S2 è almeno Opt/2.
Esercizio 1.5. Argomentare perché l’algoritmo di Sezione 8.2 non è polinomiale.
Versione: 1.13 del 6 gennaio 2007.
CAPITOLO 2
Algoritmi On-Line
In un algoritmo on-line l’input non è mostrato nella sua interezza, bensı̀ ad ogni passo
viene svelato una parte dell’input. Un algoritmo on-line ad ogni passo deve compiere una
scelta. La bontà di un algoritmo on-line è stimata confrontando la soluzione ottenuta con la
soluzione ottima calcolata dall’algoritmo off-line che conosce l’intero output. Più precisamente
denotiamo con CostA (σ) il cost della soluzione prodotta dall’algoritmo on-line A per l’istanza
σ e con Opt(σ) il costo della soluzione ottima prodotta dall’algoritmo off-line. Definiamo la
competitive ratio (rapporto di competività) ρA di A come
ρA = sup
σ
CostA (σ)
.
Opt(σ)
Alternativamente, diciamo che l’algoritmo A ha competitive ratio c se esiste una costante a ≥ 0
tale che per ogni istanza σ
CostA (σ) ≤ c · Opt(σ) + a.
1. Il problema dello sciatore
Uno sciatore deve decidere se comprare o fittare gli sci. Il costo dell’affitto degli sci per un
giorno è 1 mentre comprare gli sci costa B. Ovviamente se lo sciatore conosce il numero T di
volte in cui andrà a sciare la decisione è semplice. Il primo giorno che andrà a sciare lo sciatore
comprerà gli sci se B < T ; se invece B ≥ T allo sciatore conviene prendere gli sci in affitto.
La versione off-line del problema (quando l’intero input è noto) è quindi di facile soluzione ed
il costo della soluzione è min{T, B}.
Consideriamo invece il caso più realistico in cui lo sciatore non conosce T . Un algoritmo online deve decidere ogni volta che lo sciatore va a sciare se comprare gli sci o fittarli. Ovviamente
una volta comprati il problema non si pone. Consideriamo quindi il seguente algoritmo che
decide se lo sciatore compra o fitta gli sci l’i-esima volta che va a sciare avendo in input i, B e
T.
A(i, B, T )
if i ≤ B − 1 then affitta;
if i = B then compra;
if i > B then comprati in precedenza;
end
Calcoliamo ρA . Se T ≤ B − 1 l’algoritmo A spende T in quanto fitta gli sci per T volte
cosı̀ come l’algoritmo off-line. Se invece T ≥ B l’algoritmo spende 2B − 1 in quanto fitta gli
sci per B − 1 volte e poi li compra. In questo caso invece l’algoritmo ottimo compra gli sci il
21
22
2. ALGORITMI ON-LINE
primo giorno per un costo totale di B. Pertanto abbiamo che
2B − 1
1
ρA ≤
=2− .
B
B
Mostriamo ora che nessun algoritmo on-line ha un rapporto di competività migliore di A.
Osserviamo che un algoritmo S on-line è determinato univocamente dal numero s di giorni
dopo i quali decide di comprare gli sci. Abbiamo due casi:
(1) s ≤ B − 1. In questo caso se T = s + 1, l’algoritmo on-line spende s + B e l’algoritmo
ottimo spende s + 1. Abbiamo quindi
s+B
B−1
1
1
ρS ≥
≥1+
≥2−
≥2− .
s+1
s+1
s+1
B
(2) s > B − 1. In questo caso se T = s + 1, l’algoritmo on-line spende s + B e l’algoritmo
ottimo spende B. Abbiamo quindi
s+B
ρS ≥
≥ 2.
B
2. Ritrovare l’auto
Supponiamo di abitare su una retta. Ogni mattina dobbiamo cercare la nostra auto percheé
dimentichiamo puntualmente dove l’abbiamo parcheggiata la sera prima. Ovviamente se l’auto
si trova a distanza d dalla nostra casa l’algoritmo (off-line) che conosce la posizione impiega
tempo d per trovarla. Mostriamo ora un algoritmo (on-line) che non conosce la posizione
dell’auto e per trovare l’auto impiega al più 9d.
TrovaAuto
d = 1;
dir=sx;
repeat
vai fino a distanza d nella direzione dir;
se trovi l’auto, fine;
ritorna a casa;
d = d ∗ 2;
dir=-dir;
Il caso peggiore di questo algoritmo è quando l’auto si trova alla distanza d = 2 j + ε e
abbiamo cercato su questo lato fino a 2j e poi abbiamo cercato fino a 2j+1 dall’altro lato. In
questo caso il costo dell’algoritmo è
2(1 + 2 + 4 + · · · + 2j+1 ) + 2j + ε ≤ 9 · 2j .
3. Gestione online di liste
In questa sezione studiamo il seguente problema. Abbiamo un certo numero n di oggetti
che sono organizzati in una lista. Ad ogni passo riceviamo una richiesta per uno degli n
oggetti. Se l’oggetto richiesto si trova nella posizione i, soddisfare la richiesta ci costa i. Una
volta recuperato l’oggetto richiesto possiamo spostarlo in una qualsiasi delle posizioni tra la
testa della lista e la sua posizione originale i. Inoltre possiamo scambiare di posto due oggetti
adiacenti al costo di 1. Il nostro scopo è progettare un algoritmo on-line (e che quindi non
conosce la sequenza di richieste che dovrà soddisfare) che organizza gli elementi nella lista (e
3. GESTIONE ONLINE DI LISTE
23
cioé decide dove spostare un oggetto una volta che è stato richiesto e quali oggetti adiacenti
scambiare id posto) in modo da rendere il costo di soddisfare una sequenza di richieste il
più piccolo possibile. Osserviamo che in questo caso l’analisi worst-case non ha molto senso:
infatti il caso peggiore è ottenuto dalla sequenza che richiede sempre l’ultimo elemento della
lista e nessun algoritmo può soddisfare una sequenza di m richieste spendendo meno di O(mn).
Un’analisi piú interessante si ottiene invece confrontando il costo di un algoritmo con il costo
dell’algoritmo ottimo che conosce tutte le richieste. Assumiamo che entrambi gli algoritmi
partano con la stessa lista.
3.1. Move to Front Heuristics. In questa sezione analiziamo il seguente semplice algoritmo che chiamiamo MoveToFront: ogni volta che un oggetto è richiesto, viene spostato
all’inizio della lista. Notiamo che MoveToFront è un algoritmo om-line: ogni rischiesta è
soddisfatta senza avere alcuna conoscenza delle richieste future.
Consideriamo una sequenza R = r1 , · · · , rm di m sequenze ed indichiamo con MTF(t)
il costo di MoveToFront per soddisfare rt e con MTF(R) il costo di MoveToFront per
soddisfare la sequenza R. Indichiamo con Opt l’algoritmo ottimo che conosce l’intera sequenza
R di richieste e Opt(t) e Opt(R) sono definiti analogamente. Diciamo che una coppia (x, y)
di oggetti costituisce un’inversione se si trovano in ordine diverso tra Opt e MoveToFront.
Denotiamo inoltre con Φ(t) il numero di inversioni dopo che la richiesta rt è stata soddisfatta.
Abbiamo il seguente lemma.
Lemma 2.1. Per ogni t,
MTF(r) + Φ(t) − Φ(t − 1) ≤ 2 · Opt(t).
Prima di dimostrare Lemma 2.1 mostriamo come esso implichi il seguente teorema.
Teorema 2.2. Per ogni sequenza R di richieste MTF(R) ≤ 2 · Opt(R).
Dimostrazione.
MTF(R) =
≤
m
X
t=1
m
X
t=1
MTF(t)
(2Opt(t) − Φ(t) + Φ(t − 1))
= Φ(0) − Φ(m) + 2
m
X
Opt(t)
t=1
= Φ(0) − Φ(m) + 2 · Opt(R).
La dimostrazione è conclusa dalle osservazioni che Φ(0) = 0 e Φ(m) ≥ 0.
Passiamo ora alla dimostrazione di Lemma 2.1.
Dimostrazione. Consideriamo l’i-esima richiesta ri e denotiamo con ti la posizione dell’oggetto richiesto nella lista di MoveToFront e con si la posizione dell’oggetto richiesto nella
lista di Opt. Abbiamo quindi che MTF(i) = ti e Opt(i) = si + pi , dove pi denota il numero
di scambi effettuati dopo aver soddisfatto ri dall’algoritmo Opt (nota che MoveToFront
non effettua alcuno scambio). Abbiamo due casi.
24
2. ALGORITMI ON-LINE
Caso I: si < ti . Studiamo prima il caso in cui pi = 0. In questo caso osserviamo che il
numero di inversione che coinvolgono l’oggetto ri prima che la richiesta venga soddisfatta è
almeno ti − si . Mentre invece, siccome ri è spostato in testa alla lista, dopo che ri è stata
soddisfatta il numero di inversioni che coinvolgono ri è al più si − 1. Inoltre in questo caso
il numero di inversioni che non coinvolgono ri (essendo questo l’unico elemento spostato sia
da MoveToFront che da Opt) resta invariato. Quindi denotando con I questo numero
abbiamo che
Φ(i − 1) ≥ ti − si + I
e
Φ(i) ≤ si − 1 + I.
Da cui
MTF(i) + Φ(i) − Φ(i − 1) ≤ ti + si − 1 + I − ti + si − I
= 2si − 1
≤ 2Opt(i).
Supponiamo ora che pi > 0. Osserviamo che ciascuno dei pi scambi effettuati da Opt
incrementa Φ(i) − Φ(i − 1) al più di 1 e quindi
Quindi abbiamo
Φ(i) − Φ(i − 1) ≤ (si − 1) − (ti − si ) + pi .
MTF(i) + Φ(i) − Φ(i − 1) ≤
=
≤
=
t i + si − 1 − t i + si + pi
2si − 1 + pi
2si + 2pi
2Opt(i).
Caso II: si ≥ ti . Per ragionamenti simili a quelli usati nel caso precedente, abbiamo che
Φ(i − 1) ≥ si − ti + I e che Φ(i) ≤ si − 1 + I. Quindi abbiamo
MTF(i) + Φ(i) − Φ(i − 1) ≤
≤
≤
≤
Versione: 1.6 del 6 gennaio 2007.
t i + si − 1 + t i − si + pi
2 · t i + pi
2 · si + 2 · pi
Opt(i)
Bibliografia
[1] T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2001.
[2] Michel X. Goemans and David Williamson. New 34 -approximation algorithms for MAX SAT. SIAM Journal
on Discrete Mathematics, 7:656–666, 1994.
[3] R. L. Graham. Bounds for certain multiprocessing anomalies. Bell System Technical Journal, 45:1563–1581,
1966.
[4] R. L. Graham. Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics, 17:416–
429, 1969.
[5] D.S. Hochbaum and D.B. Shmoys. Using dual approximation algorithms for scheduling problems: theoretical
and practical results. Journal of the ACM, 34:144–162, 1987.
[6] Vijay V. Vazirani. Approximation Algorithms. Springer, 2003.
25