-
September 1st, 2011, 08:43 AM
#1
Is this minimization problem NP-Complete ?
We are given an nx(n+k) matrix A, with entries in GF(2), of the form A=(In|B) where In is a nxn identity matrix where the matrix B has no "zero" rows or columns.
The problem is to partition the columns of A into atmost m subsets each of size atmost b such that the number of "critical subset"s is minimized, where a critical subset is a subset of the set of columns such that if we remove it from A the reduced matrix has rank less than n.
The problem seems to be NP-Complete to me but not able to understand from which problem we should try to reduce.
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|