Neue Ergebnisse des Problems: Consecutive Block Minimization - Layouni, Zoubir
43,90 €
inkl. MwSt.
Versandkostenfrei*
Versandfertig in 6-10 Tagen
payback
0 °P sammeln
  • Broschiertes Buch

In diesem Buch geht es um eine besondere Eigenschaft in einer binären Matrix, die sogenannte "Eigenschaft der aufeinanderfolgenden Einsen". Ein aufeinanderfolgender Block ist eine Folge von aufeinanderfolgend angeordneten Einsen. Das Problem besteht darin, eine Permutation der Spalten zu suchen, so dass die Anzahl der aufeinanderfolgenden Blöcke in der induzierten Matrix minimal ist. Wir erinnern daran, dass das Problem für allgemeine Instanzen NP-vollständig ist, und stellen dann die Anwendungen, die es betreffen, Varianten und einen Stand der Technik vor. Unser erster Beitrag besteht darin,…mehr

Andere Kunden interessierten sich auch für
Produktbeschreibung
In diesem Buch geht es um eine besondere Eigenschaft in einer binären Matrix, die sogenannte "Eigenschaft der aufeinanderfolgenden Einsen". Ein aufeinanderfolgender Block ist eine Folge von aufeinanderfolgend angeordneten Einsen. Das Problem besteht darin, eine Permutation der Spalten zu suchen, so dass die Anzahl der aufeinanderfolgenden Blöcke in der induzierten Matrix minimal ist. Wir erinnern daran, dass das Problem für allgemeine Instanzen NP-vollständig ist, und stellen dann die Anwendungen, die es betreffen, Varianten und einen Stand der Technik vor. Unser erster Beitrag besteht darin, zu beweisen, dass CBM auch dann NP-vollständig ist, wenn die binäre Matrix nur zwei Einsen pro Zeile hat, indem wir das Problem der maximal gewichteten Hamiltonschen Kette polynomial in CBM umwandeln, das auf die betreffenden Instanzen beschränkt ist.Ein zweiter Beitrag bestand darin, die Frage zu beantworten, ob CBM mit Garantie approximierbar ist. Diese Frage wurde positiv beantwortet, indem eine polynomiale Heuristik entwickelt wurde, die Permutationen konstruiert, die zu einer Anzahl von aufeinanderfolgenden Blöcken führen, die nicht mehr als 50% vom Optimum abweichen.
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.