**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**32731

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

**Authors:**
Chaghoub Soraya,
Zhang Xiaoyan

**Abstract:**

**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.