## Abstract

We present a parallel implementation of the randomized \((1+\varepsilon )\) approximation algorithm for packing and covering linear programs presented by Koufogiannakis and Young (2007). Their approach builds on ideas of the sublinear time algorithm of Grigoriadis and Khachiyan’s (Oper Res Lett 18(2):53–58, 1995) and Garg and Könemann’s (SIAM J Comput 37(2):630–652, 2007) non-uniform-increment amortization scheme. With high probability it computes a feasible primal and dual solution whose costs are within a factor of \(1+\varepsilon \) 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 (2007).

This is a preview of subscription content, access via your institution.

## Notes

- 1.
The proper choice for initial \(\beta \) will be determined experimentally.

## References

- 1.
- 2.
Arora, S., Hazan, E., Kale, S.: The multiplicative weights update method: a meta algorithm and applications. Theory Comput.

**8**, 121–164 (2012) - 3.
Applegate, D., Archer, A., Gopalakrishnan, V., Lee, S., Ramakrishnan, K.K.: Content placement via the exponential potential function method. In: Conference on Integer Programming and Combinatorial Optimization, pp. 49–61 (2013)

- 4.
Ben-Moshe, B., Katz, M.J., Mitchell, J.S.B.: A constant-factor approximation algorithm for optimal 1.5D terrain guarding. SIAM J. Comput.

**36**(6), 1631–1647 (2007) - 5.
Bienstock, D.: Potential Function Methods for Approximately Solving Linear Programming Problems, Theory and Practice. Kluwer, Boston (2002)

- 6.
Chen, D.Z., Estivill-Castro, V., Urrutia, J.: Optimal guarding of polygons and monotone chains. In: Proceedings of the 7th Canadian Conference on Computational Geometry, pp. 133–138 (1995)

- 7.
King, J.: A 4-approximation algorithm for guarding 1.5-dimensional terrains. In: Proceedings of the 13th Latin American Symposium on Theoretical Informatics, pp. 629–640 (2006)

- 8.
Elbassioni, K., Krohn, E., Matijević, D., Mestre, J., Ševerdija, D.: Improved approximations for guarding 1.5-dimensional terrains. Algorithmica

**60**(2), 451–463 (2011) - 9.
IBM ILOG CPLEX: CPLEX Users Manual, Version 12, Release 4 (2011)

- 10.
Gurobi Optimization Inc.: Gurobi Optimizer Reference Manual (2013)

- 11.
Koufogiannakis, C., Young, N.: Beating simplex for fractional packing and covering linear programs. In: Foundations of Computer Science, 2007. FOCS’07. 48th Annual IEEE Symposium on, IEEE, pp. 494–504 (2007)

- 12.
Koufogiannakis, C., Young, N.E.: A nearly linear-time PTAS for explicit fractional packing and covering linear programs. Algorithmica

**70**(4), 648–674 (2014) - 13.
Garg, N., Könemann, J.: Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM J. Comput.

**37**(2), 630–652 (2007) - 14.
Grigoriadis, M.D., Khachiyan, L.G.: An interior-point method for bordered blockdiagonal linear programs. SIAM J. Optim.

**6**(4), 913–932 (1996) - 15.
Luby, M., Nisan, N.: A parallel approximation algorithm for positive linear programming. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of computing—STOC ’93, pp. 448–457. ACM Press, New York (1993)

- 16.
Young, N.: Sequential and parallel algorithms for mixed packing and covering. In: Proceedings 2001 IEEE International Conference on Cluster Computing, IEEE Comput. Soc, pp. 538–546 (2001)

- 17.
Kuhn, H.W., Tucker, A.W.: Review of ‘A numerical method for determination of the value and the best strategies of a zero-sum two-person game with large numbers of strategies’. In: Von Neumann, J (ed.) Collected Works, vol. 6, pp. 96–97. Pergamon Press (1963)

- 18.
Grigoriadis, M.D., Khachiyan, L.G.: A sublinear-time randomized approximation algorithm for matrix games. Oper. Res. Lett.

**18**(2), 53–58 (1995) - 19.
Young, N.: K-medians, facility location, and the Chernoff-Wald bound. In: SODA ’00 Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 86–95. SIAM (2000)

- 20.
Hong, S., Kim, S.K., Oguntebi, T., Olukotun, K.: Accelerating cuda graph algorithms at maximum warp. In: Proceedings of the 16th ACM Symposium on Principles and Practice of Parallel Programming, PPoPP ’11, pp. 267–276. ACM (2011)

- 21.
JáJá, J.: An Introduction to Parallel Algorithms. Addison-Wesley, Reading (1992)

- 22.
NVIDIA CUDA C Programming Guide

- 23.
Kirk, D.B., Hwu, W.-M.W.: Programming Massively Parallel Processors: A Hands-On Approach. Morgan Kaufmann, Los Altos (2012)

- 24.
Madry, A.: Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms. In: Symposium on the Theory of Computing, pp. 121–130 (2010)

- 25.
Plotkin, S., Shmoys, D., Tardos, E.: Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res.

**20**, 257–301 (1995) - 26.
Sanders, J., Kandrot, E.: CUDA by Example: An Introduction to General-Purpose GPU Programming, 1st edn. Addison-Wesley Professional, Reading (2010)

- 27.
Schultz, G., Meyer, R.R.: An interior-point method for block angular optimization. SIAM J. Optim.

**1**(1), 583–602 (1991) - 28.
Matias, Y., Vitter, J.S., Ni, W.: Dynamic generation of discrete random variates. Theory Comput. Syst.

**36**(4), 329–358 (2003) - 29.
Hagerup, T., Mehlhorn, K., Munro, J.I.: Optimal algorithms for generating discrete random variables with changing distributions. In: Proceedings 20th International Conference on Automata, Languages and Programming, vol. 700, pp. 253–264 (1993)

- 30.
NVIDIA CUDA SDK 2.1. Matrix multiplication

- 31.
Manshadi, F. M., Awerbuch, B., Gemulla, R., Khandekar, R., Mestre, J., Sozio, M.: A distributed algorithm for large-scale generalized matching. In: Proceedings of the 39th International Conference on Very Large Data Bases (2013)

- 32.
Awerbuch, B., Khandekar, R.: Stateless distributed gradient descent for positive linear programs. SIAM J. Comput.

**38**(6), 2468–2486 (2009)

## Acknowledgments

We would like to thank Neal E. Young for suggestions regarding the parallelization of his algorithm and for sharing the code of his sequential implementation with us. We would also like to thank Khaled Elbassioni for letting us use his lecture notes about fast approximation schemes for packing and covering LPs. Sören Laue acknowledge the support of Deutsche Forschungsgemeinschaft (DFG) under grant GI-711/5-1 within the priority program “Algorithms for Big Data”. This research was done while PatrickWijerama was at the Department of Mathematics in Osijek, Croatia, and was supported by the IAESTE Internship Program.

## Author information

### Affiliations

### Corresponding author

## Appendices

### Appendix 1: Evaluation of the Randomized Parallel Algorithm

Measurements in Tables 6 and 7 are done on 0/1 and rational matrices, respectively, where \(m\) and \(n\) denote the number of rows and columns, respectively, and \(d\) denotes the density, i.e. the probability of 1 is \(1/2^d\). Moreover, *_pp is time for preprocessing, *_cp denotes time for copying data structures from host to device and back, *_comp is time for the main while loop, *_pdg is the primal-dual gap, and ALG1, ALG2 and GUR denotes the total running time for three different approaches, namely Algorithms 1, 2 and GUROBI’s barrier method.

### Appendix 2: Evaluation of the Derandomized Parallel Algorithm

Measurements in Tables 8 and 9 are done on 0/1 and rational matrices, respectively, where \(m\) and \(n\) denote the number of rows and columns, respectively, and \(d\) denotes the density, i.e. the probability of 1 is \(1/2^d\). Moreover, *_numiter is the number of iterations, *_pdg is the primal-dual gap, and ALG1, ALG3 and GUR denotes the total running time for three different approaches, namely Algorithms 1, 3 and GUROBI’s barrier method.

### Appendix 3: Terrain Guarding Instances

In this section we will explain all the steps needed to generate arbitrary terrain guarding instances. First, we introduce some technicalities. For two points \(p=(p_x,p_y)\) and \(q=(q_x,q_y)\) in \({\mathbb {R}}^2\) we say that \(q\) is to the left (right) of \(p\), which is denoted by \(q\le p\) (\(q\ge p\)), if \(q_x\le p_x\) (\(q_x\ge p_x\)). Similarly, we say that \(q\) is strictly to the left (right) of \(p\) if \(q_x < p_x\) (\(q_x > p_x\)), which is denoted by \(q<p\) (\(q>p\)). Let \(T\) be a polygonal line that is determined by points \(P_1P_2\ldots P_n\), where \(P_i=(x_i,y_i)\in {\mathbb {R}}^2\) for \(i=1,\ldots ,n\). We say that \(T\) is a \(1.5D\) terrain of complexity \(n\) if \(T\) i \(x\)-monotone, i.e. \(P_i<P_j\) for all \(1\le i<j\le n\). We say that two points \(p\) and \(q\) on the \(1.5D\) terrain \(T\) are visible by each other, i.e. \(p\sim q\), if the line segment \(\overline{pq}\) does not intersect the terrain \(T\). Otherwise, we say that \(p\) and \(q\) are not visible by each other, i.e. \(p \not \sim q\).

For a given \(1.5D\) terrain \(T\) and a set of guards \(g\in G\subset T\) and a set of clients \(p\in N\subset T\), we label guards in \(G\) by \(1,\ldots ,n\) and clients in \(N\) by \(1,\ldots , m\). An incidence between guards \(G\) and clients \(N\) can be described with the matrix \(A\) whose elements are given by:

Visibility between \(g\in G\) and \(p\in N\) can be efficiently computed by determining the sign of the determinant that is formed by the vectors \(p, v\) and \(q\) (Fig. 8 ).

Our goal is to find the subset \(X\subset G\) with minimum number of guards such that all clients in \(N\) are visible by at least one guard in \(X\). This problem can be formulated as a set cover problem. An integer programming formulation is given by

where matrix \(A\) is defined in (20). A relaxation of the integrality constraints in (21) gives a fractional covering problem

## Rights and permissions

## About this article

### Cite this article

Jelić, S., Laue, S., Matijević, D. *et al.* A Fast Parallel Implementation of a PTAS for Fractional Packing and Covering Linear Programs.
*Int J Parallel Prog* **43, **840–875 (2015). https://doi.org/10.1007/s10766-015-0352-y

Received:

Accepted:

Published:

Issue Date:

### Keywords

- Fractional packing and covering linear programs
- Randomized algorithm
- Derandomized algorithm
- General-purpose graphics processing unit computation