Nuovi risultati per il problema

In questo libro esaminiamo una proprietà speciale di una matrice binaria nota come proprietà degli 1 consecutivi. Un blocco consecutivo è una sequenza di 1 consecutivi. Il problema consiste nel trovare una permutazione delle colonne in modo che il numero di blocchi consecutivi nella matrice indotta sia minimo. Si sottolinea che è NP-completo per istanze generali quindi si presentano le applicazioni che lo riguardano le varianti e uno stato dell'arte. Il nostro primo contributo consiste nel dimostrare che la CBM è NP-completa anche quando la matrice binaria ha solo due 1 per riga trasformando polinomialmente il problema della catena hamiltoniana di massimo peso in CBM ristretta alle istanze in questione.Un secondo contributo è consistito nel risolvere la domanda: la CBM è approssimabile con garanzia? La risposta è stata trovata sotto forma di un'euristica polinomiale che costruisce permutazioni che hanno come risultato un numero di blocchi consecutivi che non si discosta più del 50% dall'ottimo.