Block Dude Puzzles are NP-Hard (and the Rugs Really Tie the Reductions Together).
Austin BarrCalvin ChungAaron WilliamsPublished in: CCCG (2021)
Keyphrases
- np hard
- statistical modeling
- grayscale images
- special case
- scheduling problem
- optimal solution
- lower bound
- linear programming
- np complete
- closely related
- approximation algorithms
- branch and bound algorithm
- decision problems
- color images
- computational complexity
- np hardness
- co occurrence
- worst case
- image blocks
- greedy heuristic
- computationally hard
- remains np hard
- constraint satisfaction problems
- randomly generated problem instances
- crossword puzzles
- polynomial time approximation
- block wise
- block size
- efficient computation
- integer programming
- image processing
- network structure