Equipartizione di cammini nella norma L_∞

Marco Liverani (Dipartimento di Matematica, Università di Roma “La Sapienza”)
Aurora Morgana (Dipartimento di Matematica, Università di Roma “La Sapienza”)
Bruno Simeone (Dipartimento di Statistica, Probabilità e Statistiche Applicate, Università di Roma “La Sapienza”)
Giovanni Storchi (Dipartimento di Statistica, Probabilità e Statistiche Applicate, Università di Roma “La Sapienza”)

Settembre 1996

Sommario

Il problema dell'equipartizione di cammini è presente nella letteratura con diverse funzioni obiettivo e specifici algoritmi. In questo lavoro viene presentato un algoritmo basato su tecniche di shifting che determina la partizione ottima rispetto alla norma L_∞ in tempo lineare migliorando la complessità dei precedenti algoritmi basati sulla programmazione dinamica.

Introduzione

Sia P = (V,E) il cammino il cui insieme di vertici è V={1,2,...,n} e l'insieme degli spigoli è E={(1,2), (2,3), ..., (n-1,n)}. Sia 1<p<n. Una p-partizione dell'insieme V è ogni collezione π={C₁, C₂, ..., C_n} di p sottoinsiemi di V tali che ciascun elemento di V appartenga esattamente ad un solo C_k. Indichiamo con C₁, C₂, ..., C_p le componenti (cluster) della partizione π. Se una componente della p-partizione risulta vuota allora la p-partizione è detta impropria, altrimenti diremo che π è una p-partizione propria.

Una p-partizione di P è detta p-partizione connessa se ogni componente non vuota induce un sottografo connesso (sottocammino) di P. Denotiamo con Π_p(P) l'insieme di tutte le p-partizioni connesse di P.

Ad ogni vertice i del cammino è assegnato un peso non negativo w(i)>0, 1≤i≤n; chiameremo W(C_k) = ∑_{i ∈ Ck} w(i) il peso delle k-esima componente, e con m = 1/p ∑_i=1,...,n w(i) indicheremo il peso medio delle componenti della partizione π.

Un problema di equipartizione (vedi [1]) consiste nella ricerca di una partizione π* tale da minimizzare (o massimizzare) una funzione obiettivo f: Π_p(P) → R in modo da rendere il più possibile uniforme il peso delle classi W(C_k).

In questo lavoro si vuole determinare una partizione propria connessa π* che minimizzi la norma L_∞:

f(π*) = min _{π ∈ Πp(P)} f(π) = min _π∈Πp(P) max _k=1,...,p |W(C_k) - m|

Per una più ampia definizione del problema dell'equipartizione si veda Perl e Schach [5], Becker, Perl e Schach [3] ed in particolare De Simone, Lucertini, Pallottino e Simeone [4] per specifiche classi di grafi.

Questo lavoro presenta un algoritmo per l'equipartizione di un cammino nella norma L_∞ che migliora la complessità di un precedente algoritmo basato sulla programmazione dinamica (vedi [1]).

L'algoritmo

L'algoritmo inizialmente assegna i p-1 tagli ai primi p-1 spigoli del cammino, individuando così una partizione iniziale ammissibile.

Ad ogni iterazione l'algoritmo effettua lo shifting verso destra di un taglio per diminuire lo scarto dalla media m della componente di scarto massimo. Nell'effettuare questo spostamento l'algoritmo non si preoccupa che lo scarto delle altre componenti non cresca; anzi questa possibilità è prevista ed accettata dall'algoritmo che si limita a memorizzare la partizione che fino a quella iterazione aveva minimizzato il massimo scarto. Uno dei punti di forza dell'algoritmo sta proprio in questo modo di procedere un po' cieco che ad ogni passo si limita a migliorare lo scarto massimo con l'obiettivo di ridurre gli altri eventuali scarti nei passi successivi. Non si esclude che occasionalmente un'operazione di shifting dia luogo ad una classe vuota.

L'algoritmo ha termine quando risulta verificata una delle seguenti condizioni:

• Lo shifting da eseguire fa sì che l'ultima componente a destra abbia uno scarto negativo, maggiore in valore assoluto del massimo scarto che la partizione aveva prima di effettuare lo shift;
• lo shifting da eseguire fa sì che la prima componente a sinistra abbia uno scarto positivo, maggiore del massimo scarto che la partizione aveva prima di effettuare lo shift;
• la componente di massimo scarto ha uno scarto positivo ed è costituita da un unico elemento.

Si dimostra che al termine dell'esecuzione la partizione generata è ottima.

La dimostrazione di correttezza dell'algoritmo si basa su una generalizzazione della proprietà di "aboveness" investigata in [5] e [3]: date due p-partizioni π e π' di P si dice che π' è "al di sopra di" (above) π se per ogni taglio k, il k-esimo taglio di π è sopra il k-esimo taglio di π' (il vertice 1 si considera quello più in alto ed il vertice n quello più in basso), i due tagli possono anche insistere su uno stesso arco. La proprietà di "stare al di sopra" individua un ordinamento parziale nell'insieme delle partizioni.

Il risultato cruciale è il seguente

Teorema: Se π è una qualunque delle partizioni generate dall'algoritmo, allora esiste sempre una partizione ottima π* tale che o π è al di sopra di π* o π* è al di sopra di π.

Complessità

L'algoritmo effettua (p-1)(n-p) operazioni di shift e ad ogni operazione deve determinare la componente di peso massimo, in O(log p) passi; pertanto si ha una complessità dell'ordine di p (n-p) log p. Il caso peggiore per l'algoritmo si presenta per p=n/2, la complessità allora diviene O(n² log n/2) che comunque migliora la complessità dell'algoritmo di programmazione dinamica (O(n²p) = O(n³)).

È interessante notare che l'algoritmo possiede "buoni freni" nel senso che una volta generata la partizione ottima, esso richiede al più p-1 iterazioni prima di riconoscerla come tale ed arrestarsi.

Inoltre, se il numero di tagli (p-1) si considera fissato (ed in genere nelle applicazioni essendo p << n si può assumere p come una costante), la complessità dell'algoritmo risulta O(n).

Ci proponiamo di utilizzare un'analoga metodologia per risolvere il caso più generale di equipartizione su alberi.

Bibliografia

[1] E.L.Aparo, B.Simeone, Un algoritmo di equipartizione e il suo impiego in un problema di contrasto ottico, Ricerca Operativa, 3: 31-42, 1973.

[2] R.I.Becker, Y.Perl, Shifting algorithms for tree partitioning with general weighting functions, J. of Algorithms, 4: 101-120, 1983.

[3] R.I.Becker, Y.Perl, S.R.Shach, A shifting algorithm for min-max tree partitioning, J.of ACM, 29: 58-67, 1982.

[4] C.De Simone, M.Lucertini, S.Pallottino, B.Simeone, Fair disconnections of spiders, worms and caterpillars, Networks, 20: 323-344, 1990.

[5] Y.Perl, S.R.Schach, Max-min tree partitioning, J. of ACM, 28: 5-15, 1981.

[6] Y.Perl, U.Vishkin, Junction tree structure with application to a shifting algorithm, Discrete Applied Mathematics, 12: 71-80, 1985.

[7] B.Simeone, Optimal graph partitioning, Atti delle Giornate di Lavoro AIRO, Urbino: 57-73, 1978.

Questo testo è tratto dagli atti delle Giornate di Lavoro AIRO 96 - Perugia, 16-20 Settembre 1996.