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.