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

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.

Authors:

• Chaghoub Soraya
• Zhang Xiaoyan

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.