Noisy Data Make the Partial Digest Problem NP-hard.
Mark CieliebakStephan J. EidenbenzPaolo PennaPublished in: WABI (2003)
Keyphrases
- noisy data
- np hard
- noise tolerant
- optimal solution
- scheduling problem
- noise free
- np complete
- special case
- missing data
- approximation algorithms
- high dimensional
- lower bound
- intrinsic dimensionality
- computational complexity
- worst case
- learning from noisy data
- neural network
- constraint satisfaction problems
- greedy heuristic
- input data
- high dimensionality
- training data
- pattern recognition
- computer vision