Fast Parallel Implementation of Fractional Packing and Covering Linear Programs
Department of Mathematics, J. J. Strossmayer University of Osijek, Croatia
J. J. Strossmayer University of Osijek, 2012
@article{jelic2012fast,
title={Fast Parallel Implementation of Fractional Packing and Covering Linear Programs},
author={Jeli{‘c}, S. and Laue, S. and Matijevi{‘c}, D. and Wijerama, P.},
year={2012}
}
We present a parallel implementation of the randomized (1 + e)-approximation algorithm for packing and covering linear programs presented by Koufogiannakis and Young [4]. In order to make the algorithm more parallelizable we also implemented a deterministic version of the algorithm, i.e. instead of updating a single random entry at each iteration we updated deterministically many entries at once. This slowed down a single iteration of the algorithm but allowed for larger step sizes which lead to fewer iterations. We use NVIDIA’s parallel computing architecture CUDA for the parallel environment. We report a speedup over the times reported by Koufogiannakis and Young [4] between one and two orders of magnitude.
October 13, 2012 by hgpu
