Title :
Using an unrank framework to solve small instances of NP-hard problems on graphical processing units
Author :
Vogel, N. ; Uhen, Colin ; Burnside, Zachary ; Botero, Sergio ; Trefftz, Christian ; Wolffe, Greg
Author_Institution :
Sch. of Comput., Grand Valley State Univ., Allendale, MI, USA
Abstract :
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.
Keywords :
computability; computational complexity; electrical engineering computing; graph colouring; graphics processing units; 3-SAT problem; NP-hard problems; Unrank framework; electrical engineering; exponential time complexity; graph coloring problem; graphical processing units; heuristical approach; maximum clique problem; Color; Encoding; Graphics processing units; Kernel; Libraries; NP-hard problem; Space exploration; GPU NP-complete; unrank;
Conference_Titel :
Electro/Information Technology (EIT), 2014 IEEE International Conference on
Conference_Location :
Milwaukee, WI
DOI :
10.1109/EIT.2014.6871814
