Reconstructing 3-colored grids from horizontal and vertical projections is NP-hard
Christoph DürrFlavio GuiñezMartín MatamalaPublished in: CoRR (2009)
Keyphrases
- np hard
- horizontal and vertical projections
- discrete sets
- discrete tomography
- np hardness
- approximation algorithms
- optimal solution
- scheduling problem
- lower bound
- integer programming
- computational complexity
- special case
- np complete
- linear programming
- greedy heuristic
- knapsack problem
- convex sets
- grid computing
- worst case
- convex optimization
- lagrangian relaxation
- binary variables
- dimensionality reduction