Nowe wyniki dla problemu

W tej książce przyjrzymy się specjalnej właściwości macierzy binarnych znanej jako właściwość kolejnych 1. Kolejny blok to sekwencja kolejno położonych jedynek. Problem polega na znalezieniu takiej permutacji kolumn aby liczba kolejnych bloków w indukowanej macierzy była minimalna. Wskazujemy że jest on NP-zupełny dla ogólnych przypadków a następnie przedstawiamy zastosowania które go dotyczą warianty i aktualny stan wiedzy. Nasz pierwszy wkład polega na udowodnieniu że CBM jest NP-zupełne nawet wtedy gdy macierz binarna ma tylko dwie jedynki na wiersz poprzez wielomianowe przekształcenie problemu łańcucha Hamiltona o maksymalnej wadze do CBM ograniczonego do omawianych przypadków.Drugi wkład polegał na rozwiązaniu pytania: czy CBM jest aproksymowalny z gwarancją? Odpowiedź została znaleziona w postaci wielomianowej heurystyki która konstruuje permutacje skutkujące liczbą kolejnych bloków nie większą niż 50% od optimum.