The three column Bandpass problem is solvable in linear time

AbstractThe general Bandpass problem is NP-hard and was claimed to be NP-hard when the number of columns is three. Previously we designed a polynomial time row-stacking algorithm for the three column case, to produce a solution that is at most 1 less than the optimum. We show in this paper that for any bandpass number B≥2, an optimal solution is always achievable in linear time