Rigid Foldability is NP-Hard.
Hugo A. AkitayaErik D. DemaineTakashi HoriyamaThomas C. HullJason S. KuTomohiro TachiPublished in: CoRR (2018)
Keyphrases
- np hard
- approximation algorithms
- lower bound
- optimal solution
- scheduling problem
- special case
- integer programming
- np complete
- worst case
- linear programming
- decision problems
- remains np hard
- greedy heuristic
- branch and bound algorithm
- closely related
- real time
- computational complexity
- three dimensional
- knapsack problem
- minimum cost
- np hardness
- constraint satisfaction problems
- data structure
- decision trees
- information retrieval
- data mining
- data sets
- set cover
- boolean variables