Article ID: | iaor20041209 |
Country: | Netherlands |
Volume: | 31 |
Issue: | 5 |
Start Page Number: | 350 |
End Page Number: | 356 |
Publication Date: | Sep 2003 |
Journal: | Operations Research Letters |
Authors: | Reinelt Gerhard, Oswald Marcus |
Keywords: | combinatorial analysis |
The NP-hard weighted consecutive ones problem consists of converting a given 0/1-matrix to a consecutive ones matrix by switching entries with a minimum total cost. Here we consider this problem when the number of rows or columns is fixed. We show that in this case the problem can be solved in polynomial time.