8348

Fast Parallel Implementation of Fractional Packing and Covering Linear Programs

Slobodan Jelic, Soren Laue, Domagoj Matijevic, Patrick Wijerama
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}

}

Download Download (PDF)   View View   Source Source   

1686

views

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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2024 hgpu.org

All rights belong to the respective authors

Contact us: