Nouveaux résultats du problème

Dans ce livre on s'intéresse à une propriété spéciale dans une matrice binaire dite propriété de consécutivité des 1 . Un bloc consécutif est une séquence de 1 situés consécutivement. Le problème consiste à chercher une permutation des colonnes de sorte que le nombre de blocs consécutifs dans la matrice induite soit minimum. On rappelle qu'il est NP-complet pour des instances générales puis on présente les applications qui le concernent les variantes et un état de l'art. Notre première contribution consiste à prouver que CBM est NP-complet même lorsque la matrice binaire n'a que deux 1 par ligne en transformant polynomialement le problème de la chaîne hamiltonienne de poids maximum à CBM restreint aux instances en question.Une seconde contribution a consisté à résoudre cette question: CBM est-il approximable avec garantie ? On y a répondu favorablement en mettant au point une heuristique polynomiale construisant des permutations aboutissant à un nombre de blocs consécutifs ne s'écartant pas de plus de 50% de l'optimum.