New problem results - Layouni, Zoubir
29,99 €
inkl. MwSt.
Versandkostenfrei*
Versandfertig in 6-10 Tagen
payback
15 °P sammeln
  • Broschiertes Buch

In this book, we focus on a special property in a binary matrix, known as the "1-consecutive property". A consecutive block is a sequence of consecutively located 1s. The problem is to find a permutation of the columns so that the number of consecutive blocks in the induced matrix is minimal. We point out that it is NP-complete for general instances, then we present applications to it, variants and a state of the art. Our first contribution consists in proving that CBM is NP-complete even when the binary matrix has only two 1's per row, by polynomially transforming the maximum-weight…mehr

Andere Kunden interessierten sich auch für
Produktbeschreibung
In this book, we focus on a special property in a binary matrix, known as the "1-consecutive property". A consecutive block is a sequence of consecutively located 1s. The problem is to find a permutation of the columns so that the number of consecutive blocks in the induced matrix is minimal. We point out that it is NP-complete for general instances, then we present applications to it, variants and a state of the art. Our first contribution consists in proving that CBM is NP-complete even when the binary matrix has only two 1's per row, by polynomially transforming the maximum-weight Hamiltonian chain problem to CBM restricted to the instances in question.A second contribution consisted in solving the question: is CBM approximable with guarantee? The answer was found in the form of a polynomial heuristic that constructs permutations leading to a number of consecutive blocks within 50% of the optimum.
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.