Nouveaux résultats du problème : Consecutive Block Minimization - Layouni, Zoubir
29,99 €
inkl. MwSt.
Versandkostenfrei*
Versandfertig in 6-10 Tagen
payback
15 °P sammeln
  • Broschiertes Buch

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

Andere Kunden interessierten sich auch für
Produktbeschreibung
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.
Autorenporträt
Dr. Zoubir Layouni a obtenu un doctorat en informatique en 2010 à l'Université Badji Mokhtar d'Annaba, en Algérie. Il est actuellement Professeur des universités et Vice-Doyen de la faculté. Ses recherches portent sur l'optimisation, les algorithmes d'approximation et les problèmes NP-difficiles.