Polynomial-time local-improvement algorithm for Consecutive Block Minimization

A block of consecutive ones (bco for short) in a binary m×n-matrix is any maximal sequence of consecutive ones occurring in the same row. We consider the Consecutive Block Minimization (CBM) problem in which the aim is to minimize the number of bco's by permuting the matrix's columns. The paper introduces a pair of O(n2)-sized local search neighborhoods in which the number of bco's of a neighbor is computed in O(m) time. The performance of a local-search algorithm is then evaluated on some real-world and some randomly-generated instances of the problem.