BROWSE
Detail
Conference Paper
A Design of a GPU Based Solver for Quadratic Assignment Problems
Cited 0 time in 
Share 
Share
- Authors
- Hyunjoong Kang, Yeonhee Lee, Hyun Yoe
- Issue Date
- 2024-10
- Citation
- International Conference on Information and Communication Technology Convergence (ICTC) 2024, pp.635-640
- Publisher
- IEEE
- Language
- English
- Type
- Conference Paper
- Abstract
- Many real-world allocation problems can be formulated as quadratic assignment problems (QAPs) that are NP-hard and lack polynomial-time approximations. While several heuristic algorithms have been developed, no clear and general solution method has been devised to date. In fact, the solution quality and runtime fluctuate depending on the QAP instances to be solved. We introduce a GPU (graphics processing unit)-based method to solve QAPs. A novel scalable softmax function is designed to generate a two-dimensional assignment matrix in O time with parallelization, where n is the problem size. Owing to recent advancements in GPUs, our method shows shorter runtime with similar solution quality when compared with the best existing algorithms.
- KSP Keywords
- Heuristic algorithm, Polynomial time, Quadratic assignment problems, Real-world, Softmax Function, Solution quality, allocation problem, general solution, graphics processing units(GPUs), np-hard, similar solution