Reconstructing 3-Colored Grids from Horizontal and Vertical Projections Is NP-hard.
Christoph DürrFlavio GuiñezMartín MatamalaPublished in: ESA (2009)
Keyphrases
- np hard
- horizontal and vertical projections
- discrete sets
- discrete tomography
- np hardness
- scheduling problem
- np complete
- optimal solution
- linear programming
- special case
- approximation algorithms
- integer programming
- greedy heuristic
- lower bound
- computational complexity
- grid computing
- worst case
- image processing
- knapsack problem