Novos resultados para o problema: Minimização de blocos consecutivos
Versandkostenfrei!
Versandfertig in 6-10 Tagen
28,99 €
inkl. MwSt.
PAYBACK Punkte
14 °P sammeln!
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 do...
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.
Andere Kunden interessierten sich für
