Neue Ergebnisse des Problems

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.