Ricerc@Sapienza

In questa ricerca ci si propone di studiare una classe di problemi di partizione connessa ottima di grafi in cui la funzione obiettivo è basata sul gap delle componenti, definito come la differenza tra il valore massimo e il valore minimo di pesi associati agli elementi di una componente.

Si tratta di problemi che nel caso generale sono difficili da risolvere (NP-hard) e si vuole sia indagare sulla complessità su grafi a albero, sia sperimentare la performance di alcune formulazioni di programmazione matematica a variabili 0-1 per i problemi su grafi arbitrari.

Si intende inoltre studiare nuovi metodi di soluzione per il problema della bipartizione di un grafo con più criteri, utilizzando un approccio di programmazione matematica basato sulla formulazione del problema del taglio minimo di una rete e in grado di fornire soluzioni Pareto ottime o con tecniche di scalarizzazione o con nuovi algoritmi specifici.