Constant Factor Approximation Algorithm for p-Median Network Design Problem with Multiple Cable Types

Authors: Chaghoub Soraya, Zhang Xiaoyan

Abstract:

This research presents the first constant approximation algorithm to the p-median network design problem with multiple cable types. This problem was addressed with a single cable type and there is a bifactor approximation algorithm for the problem. To the best of our knowledge, the algorithm proposed in this paper is the first constant approximation algorithm for the p-median network design with multiple cable types. The addressed problem is a combination of two well studied problems which are p-median problem and network design problem. The introduced algorithm is a random sampling approximation algorithm of constant factor which is conceived by using some random sampling techniques form the literature. It is based on a redistribution Lemma from the literature and a steiner tree problem as a subproblem. This algorithm is simple, and it relies on the notions of random sampling and probability. The proposed approach gives an approximation solution with one constant ratio without violating any of the constraints, in contrast to the one proposed in the literature. This paper provides a (21 + 2)-approximation algorithm for the p-median network design problem with multiple cable types using random sampling techniques.

Keywords: Approximation algorithms, buy-at-bulk, combinatorial optimization, network design, p-median.

References:

[1] A. Agrawal, P. Kelin and R. Ravi, When trees collide: An approximation algorithm for the generalized steiner problem on networks. SIAM J. Comput, 1995.
[2] A. Gupta, A. Kumar and T. Rougharden, Simpler and better approximation algorithms for network design, 35th ed. ACM sympos, on the theory of comput, Sna Diego, CA, 2003.
[3] A. Hassin, R. Ravi and F.S. Salman, Approximation algorithm for capacitated network design problem. Algorithmica, 2006.
[4] B. Awerbuch and Y. Azar, Buy-at-bulk network design, 38th ed. in Proc.IEEE Symposium on foundations of Computer Science (FOCS), 1997.
[5] C. Selene, M. Vallejo and J. Fernando, Solving the p-median bilevel problem with order through a hybrid heuristic . Applied Soft Computing, 2017.
[6] C. Swamy, Improved approximation algorithms for matroid and knapsack median problems and applications. ACM Transactions on Algorithms, 2016.
[7] C. Swamy and A. Kumar, Primal dual algorithms for connected facility location problems. Algorithmica, 2004.
[8] C. Wu, D. Du and D. Xu, An approximation algorithm for the k-median problem with uniform penalties via pseudo-solution. Theoretical Computer Science, 2018.
[9] G. Blelloch, A. Gupta and K. Tangwoongsan, Parallel probabilistic tree embedding, k-median and buy-at-bulk network design. 24th ed. ACM Symposium on Parallelism in Algorithms and Architectures-SPAA, 2012.
[10] J. Byrka and K. Aardal, An improved LP-based approximation for the steiner tree, 10th ed. Proceedings of the forty-second ACM symposium on Theory of computing, 2010.
[11] K. Talwar, Single-sink buy-at-bulk LP has constat integrality gap, 9th ed . in Proc. International Conference on integer Programming and Combinatorial Optimization (IPCO), 2002.
[12] F. S. salman, J. Cheryan, R. Ravi and S. Subramanian, Approximating the single-sink link installation problem in network design. SIAM J. Optim, 2000.
[13] N. Garg, R. Khandekar, G. Konjevod, R. Ravi, F. S. Salman, A. Sinha On the integrality gap of natural formulation of the single-sink buy-at-bulk network design problem, 8th ed. International Conference on Integer programming and Combinatorial Optimization (IPCO), 2001.
[14] P. kaveh, Solving capacitated p-median problem by hybrid k-median clustering and FNS algorithm. International journal of Innovation, 2010.
[15] R. Jpothi and B. Raghavachari, Improved approximation algorithms for the single-sink buy-at-bulk network design problems. Journal of Discrete Algorithms, 2009.
[16] R. Ravi and S. Sinha, Approximation algorithms combining facility location and network design. Oper. Rzs, 2006.
[17] S. C. Chang, W. C. K. Yen, Y. L. Wang and J. J. Liu, J. J, The NP-hardness of the connected p-median problem on bipartie graphs and split graphs. Chiang Mai J. Sci,2003.
[18] S. Guha, A. Meyerson and k. Mungala, A constant factor approximation for the single sink edge installation problem . SIAM J.Comput, 2009.
[19] S. Li and O. Svensson, Approximating k-median via pseudo-approximation, 45th ed . Proceedings of the 45th annual ACM symposium on Symposium on theory of computing-STOC, 2013.
[20] Z. Drezner, J. Brimberg, N. Mladenovi´c and S. Salhi Solving the planar p-median problem by variable neighborhood and concentric searches. Journal of Global Optimization, 2015.