Novos resultados para o problema

Neste livro analisamos uma propriedade especial de uma matriz binária conhecida como a propriedade do 1 consecutivo. Um bloco consecutivo é uma sequência de 1s localizados consecutivamente. O problema é encontrar uma permutação das colunas de modo a que o número de blocos consecutivos na matriz induzida seja mínimo. Salientamos que é NP-completo para instâncias gerais depois apresentamos as aplicações que lhe dizem respeito as variantes e um estado da arte. A nossa primeira contribuição consiste em provar que o MFC é NP-completo mesmo quando a matriz binária tem apenas dois 1's por linha transformando polinomialmente o problema da cadeia hamiltoniana de peso máximo em MFC restrito às instâncias em questão.Uma segunda contribuição consistiu em resolver a questão: é a CBM aproximável com garantia? A resposta foi encontrada sob a forma de uma heurística polinomial que constrói permutações que resultam num número de blocos consecutivos que não difere mais de 50% do ótimo.