Premium
A note on the NP–hardness of the consecutive block minimization problem
Author(s) -
Haddadi Salim
Publication year - 2002
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/1475-3995.00387
Subject(s) - minification , block (permutation group theory) , combinatorics , mathematics , binary number , np complete , mathematical optimization , algorithm , computer science , arithmetic , time complexity
We show that consecutive block minimization problem is NP–hard even when restricted to binary matrices that have two ones per row.