Reconstructing a Matrix with a Given List of Coefficients and Prescribed Row and Column Sums Is NP-Hard.
Yan GérardPublished in: IWCIA (2008)
Keyphrases
- binary matrix
- binary matrices
- np hard
- matrix factorization
- optimal solution
- low rank
- approximation algorithms
- special case
- np complete
- lower bound
- worst case
- minimum cost
- scheduling problem
- linear programming
- np hardness
- remains np hard
- integer programming
- ranked list
- decision problems
- linear combination
- knapsack problem
- computationally hard
- maximum weight
- polynomial time approximation
- closely related
- neural network