Using an unrank framework to solve small instances of NP-hard problems on graphical processing units
Nicholas Vogel, Colin Uhen, Zachary Burnside, Sergio Botero, Christian I. Trefftz, Greg Wolffe · IEEE International Conference on Electro Information Technology · 2014
Certain problems encountered in electrical engineering incur an exponential time complexity and are therefore impossible to solve exactly for all problem sizes. However, heuristical approaches can sometimes use exact solutions of small instances of a problem to formulate a suboptimal solution to a larger instance of the problem. This paper demonstrates how to use the Unrank algorithm to solve small instances of several NP-hard problems (3-SAT, Maximum Clique and Graph Coloring) on a Graphical Processing Unit.