Approximation theory in combinatorial optimization. Application to the generalized minimum spanning tree problem
DOI:
https://doi.org/10.33993/jnaat341-795Keywords:
generalized minimum spanning tree problemAbstract
We present an overview of the approximation theory in combinatorial optimization. As an application we consider the Generalized Minimum Spanning Tree (GMST) problem which is defined on an undirected complete graph with the nodes partitioned into clusters and non-negative costs are associated to the edges. This problem is NP-hard and it is known that a polynomial approximation algorithm cannot exist. We present an in-approximability result for the GMST problem and under special assumptions: cost function satisfying the triangle inequality and with cluster sizes bounded by \(\rho\), we give an approximation algorithm with ratio \(2 \rho\).Downloads
References
Dror, M. and Haouari, M., Generalized Steiner problem and other variants, J. Combinatorial Optimization, 4, pp. 415-436, 2000, https://doi.org/10.1023/a:1009881326671 DOI: https://doi.org/10.1023/A:1009881326671
Dror, M., Haouari, M. and CHAOUACHI J., Generalized spanning trees, EJOR, 120, pp. 583-592, 2000, https://doi.org/10.1016/s0377-2217(99)00006-5 DOI: https://doi.org/10.1016/S0377-2217(99)00006-5
Feremans, C., Labbe, M. and Laporte, G., A comparative analysis of several formulations for the generalized minimum spanning tree problem, Networks, 39 (1), pp. 29-34, (2002), https://doi.org/10.1002/net.10009 DOI: https://doi.org/10.1002/net.10009
Feremans, C. and Grigoriev, A., An Approximation Scheme for the Generalized Geometric Minimum Spanning Tree Problem with Grid Clustering, preprint, 2004.
Garg, N., Konjevod, G. and Ravi, R., A polylogarithmic algorithm for the group Steiner tree problem, J. of Algorithms, 37 (1), pp. 66-84, 2000, https://doi.org/10.1006/jagm.2000.1096 DOI: https://doi.org/10.1006/jagm.2000.1096
Goemans, M.X and Bertsimas, D.J., Survivable networks, linear programming relaxations and parsimonious property, Mathematical programming, 60, pp. 145-166, 1993, https://doi.org/10.1007/bf01580607 DOI: https://doi.org/10.1007/BF01580607
Grötschel, M., Discrete mathematics in manufacturing, Preprint SC 92-3, ZIB, 1992.
Grötschel, M., Lovász, L. and Schrijver, A., Geometric Algorithm and Combinatorial Optimization, Springer Verlag, Berlin, 1988, https://doi.org/10.1007/978-3-642-97881-4 DOI: https://doi.org/10.1007/978-3-642-97881-4
Lovász, L., On some connectivity properties of Eulerian graphs, Acta Mathematica Acad. Scient. Hungaricae, 28, pp. 129-138, 1976, https://doi.org/10.1007/bf01902503 DOI: https://doi.org/10.1007/BF01902503
Myung, Y.S., Lee, C.H. and Tcha, D.W., On the Generalized Minimum Spanning Tree Problem, Networks, 26, pp. 513-623, 1995. DOI: https://doi.org/10.1002/net.3230260407
Penn, M. and Rozenfeld S., Approximation algorithm for the group Steiner network problem, Technical report, Faculty of Industrial Engineering, Haifa, Israel, Oct. 2003.
Pop, P.C., The Generalized Minimum Spanning Tree Problem, PhD thesis, University of Twente, The Netherlands, 2002. DOI: https://doi.org/10.1016/S0377-2217(02)00213-8
Pop, P.C., New Models of the Generalized Minimum Spanning Tree Problem, Journal of Mathematical Modelling and Algorithms, 3, no. 2, pp. 153-166, 2004, https://doi.org/10.1023/b:jmma.0000036579.83218.8d DOI: https://doi.org/10.1023/B:JMMA.0000036579.83218.8d
Salazar, J.J., A note on the generalized Steiner tree polytope, Discrete Appl. Math. 100, nos. 1-2, pp. 137-144, 2000, https://doi.org/10.1016/s0166-218x(99)00200-0 DOI: https://doi.org/10.1016/S0166-218X(99)00200-0
Schrijver, A., Combinatorial Optimization, Springer-Verlag, Berlin, 2003.
Slavik, P., On the approximation of the generalized Traveling salesman problem, preprint, 1999.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2015 Journal of Numerical Analysis and Approximation Theory
This work is licensed under a Creative Commons Attribution 4.0 International License.
Open Access. This article is distributed under the terms of the Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
