Algoritmi Approssimati

ALBERTO CAPRARA, ROMEO RIZZI,
Improved Breakpoint Graph Decompositions,
submitted
descrizione: Il sorting by reversals é uno di quei problemi in biologia computazionale che sono venuti alla luce con lo sviluppo del Progetto Genoma Umano. L'interesse per questo problema da parte della biologia computazionale é forte. Caprara aveva purtroppo dimostrato che il problema era NP-hard. Sorge a questo punto l'interesse per degli algoritmi di tipo approssimato. Questi sono intesi a produrre delle soluzioni che, se non ottime, siano quantomeno di provata qualitá, ossia di qualitá superiore ad un certo bound fissato. Noi si é migliorato il miglior bound attuale. Il tutto a prezzo di un'analisi combinatorica di non poco peso per il lettore e per chi mai volesse implementare l'algoritmo. La complessitá computazionale dell'algoritmo tuttavia non ne ha sofferto.

ROMEO RIZZI,
On the Steiner tree $\frac{3}{2}$-approximation for quasi-bipartite graphs,
submitted
.ps file descrizione: Dato un insieme di nodi, un albero di Steiner deve toccarli tutti. Il problema é quello di trovare un albero di Steiner di peso minimo. Questo problema, originariamente studiato da Gauss, é NP-hard. La ricerca di algoritmi approssimati per questo problema é fervida ed appassionata. In un lavoro assai di voga, Rajagopalan e Vazirani avevano proposto un algoritmo $(\frac{3}{2}+\epsilon)$-approssimato nel caso di grafi quasi bipartiti, ossia quando ogni arco ha almeno un'estremitá in un nodo richiesto. Noi diamo un algoritmo $\frac{3}{2}$-approssimato ed assai piú semplice per lo stesso problema. Inoltre, contrariamente all'algoritmo di Rajagopalan e Vazirani, la nostra soluzione é effettivamente pratica.

ALBERTO CAPRARA, ROMEO RIZZI,
Improving a Family of Approximation Algorithms to Edge Color Multigraphs,
Inf. Proc. Lett. 68 (1998) 11-15.
.ps file descrizione: Coloriamo gli archi di un grafo in modo che archi incidenti ad uno stesso nodo abbiano colori diversi. Evidentemente non possiamo sperare di impiegare meno di $\Delta$ colori, ove $\Delta$ é il massimo grado di un nodo. Il teorema di Vizing dice che possiamo sempre farcela con $\Delta+1$ colori. Tuttavia ció non é piú vero ove si consideri la possibilitá di avere archi paralleli tra una stessa copia di nodi. É stato tuttavia definito un parametro $\Delta'$, di facile computazione, che costituisce una miglior stima inferiore che non $\Delta$ sul numero di colori necessari. Delle famigerate congetture degli anni 80 affermano poi che ce la si puó sempre fare con al piú $\Delta'+1$ colori. In ogni caso, il problema di colorare gli archi con pochi colori ha importanti applicazioni. Questo spiega la serie di algoritmi che sono stati via via presentati per impiegare al piú $\alpha \Delta'$ colori. Purtroppo, ogni nuovo algoritmo se ne esce con un valore di $\alpha$ piú vicino ad 1, ma anche con una complessitá computazionale e di implementazione sempre maggiore. Noi abbiamo mostrato come con un semplice trucco fosse possibile migliorare il grado di approssimazione per ciascuno degli algoritmi sinora proposti senza incrementarne la complessitá. Ció consente di dedurre la validitá della congettura di cui sopra per $\Delta\leq 12$.

ALBERTO CAPRARA, ALESSANDRO PANCONESI, ROMEO RIZZI,
Packing triangles in planar graphs,
ready for submission
descrizione: Dato un grafo planare, vogliamo trovare in esso il massimo numero di triangoli disgiunti. A seconda che li si voglia solamente disgiunti sui nodi od anche sugli archi abbiamo due distinti problemi. Tuttavia, in una trattazione assai unificata, diamo dei PTAS per entrambi i problemi avvalendoci del teorema separatore. Un PTAS é un algoritmo approssimante a qual si voglia precisione ed é in pratica il meglio che si possa sperare quando il problema in questione risulti essere NP-hard. In effetti noi si dimostra inoltre che entrambi i problemi sono NP-hard. Precedentemente solamente il caso di triangoli disgiunti sui nodi era noto essere tale e la dimostrazione basava su una ben piú complessa riduzione che non quella da noi proposta.

ALBERTO CAPRARA, ALESSANDRO PANCONESI, ROMEO RIZZI,
Packing Cuts in Graphs,
in preparation
descrizione: Diamo svariati risultati di inapprossimabilitá per il problema di trovare il maggior numero possibile di tagli disgiunti in un dato grafo. La questione dell' NP-hardness del problema era stata recentemente posta al centro dell'attenzione da alcuni lavori di Ajeev, ma segue ora come conseguenza di questi ben piú forti risultati. (Non approssimabilitá entro un fattore $\log n$ nel caso generale ed APX-hardness in svariati casi particolari). Diamo altresí degli algoritmi approssimati che mostrano come tali risultati siano stretti.