Seminar za računarstvo i primenjenu matematiku, 24. novembar 2015.

• 23. Novembar,  2015
• Komentari (0)

Naredni sastanak Seminara za biće održan u utorak, 24. novembra 2015. u sali 301f Matematičkog instituta SANU sa početkom u 14:15 časova.

Predavač: Slobodan Jelić, University of Osijek, Department of Mathematics

Naslov predavanja: A FAST PARALLEL IMPLEMENTATION OF A PTAS FOR FRACTIONAL PACKING AND COVERING LINEAR PROGRAMS

Apstrakt: In this lecture, a parallel implementation of the randomized (1+eps)-approximation algorithm for packing and covering linear programs given by Koufogiannakis and Young (2007, 2013) will be presented. Their approach builds on ideas of the sublinear time algorithm of Grigoriadis and Khachiyan`s (1995) and Garg and Konemann`s (1998) non-uniform-increment amortization scheme.

With high probability it computes a feasible primal and dual solution whose costs are within a factor of (1+eps) of the optimal cost. In order to make their 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 between one and two orders of magnitude over the times reported by Koufogiannakis and Young in 2013.

This is a joint work with Domagoj Matijevic, Soren Laue and Patrick Wijerama.

---