A GPU-enabled solver for time-constrained linear sum assignment problems

Roverso, Roberto and Naiem, Amgad and El-Beltagy, Mohammed and El-Ansary, Sameh and Haridi, Seif (2010) A GPU-enabled solver for time-constrained linear sum assignment problems. In: Informatics and Systems (INFOS), 2010 The 7th International Conference., 28-30 March 2010, Cairo, Egypt.


Official URL:


This paper deals with solving large instances of the Linear Sum Assignment Problems (LSAPs) under realtime constraints, using Graphical Processing Units (GPUs). The motivating scenario is an industrial application for P2P live streaming that is moderated by a central tracker that is periodically solving LSAP instances to optimize the connectivity of thousands of peers. However, our findings are generic enough to be applied in other contexts. Our main contribution is a parallel version of a heuristic algorithm called Deep Greedy Switching (DGS) on GPUs using the CUDA programming language. DGS sacrifices absolute optimality in favor of a substantial speedup in comparison to classical LSAP solvers like the Hungarian and auctioning methods. We show the modifications needed to parallelize the DGS algorithm and the performance gains of our approach compared to a sequential CPU-based implementation of DGS and a mixed CPU/GPU-based implementation of it.

Item Type:Conference or Workshop Item (Paper)
ID Code:4096
Deposited By:Roberto Roverso
Deposited On:10 Feb 2011 15:41
Last Modified:10 Feb 2011 15:41

Repository Staff Only: item control page