Novos resultados para o problema - Layouni, Zoubir
29,99 €
inkl. MwSt.
Versandkostenfrei*
Versandfertig in 6-10 Tagen
payback
15 °P sammeln
  • Broschiertes Buch

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…mehr

Andere Kunden interessierten sich auch für
Produktbeschreibung
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.
Autorenporträt
O Dr. Zoubir Layouni obteve um doutoramento em ciências informáticas em 2010 pela Université Badji Mokhtar em Annaba, Argélia. Atualmente, é Professor Universitário e Vice-Diretor da Faculdade. Os seus interesses de investigação incluem a otimização, os algoritmos de aproximação e os problemas NP-difíceis.