Using an unrank framework to solve small instances of NP-hard problems on graphical processing units

摘要

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.