Approximation theory in combinatorial optimization. Application to the generalized minimum spanning tree problem

Authors

  • Petrică C. Pop North University of Baia Mare, Romania
  • G. Still University of Twente, Netherlands
  • W. Kern University of Twente, Netherlands

DOI:

https://doi.org/10.33993/jnaat341-795

Keywords:

generalized minimum spanning tree problem
Abstract views: 174

Abstract

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

Download data is not yet available.

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

2005-02-01

How to Cite

Pop, P. C., Still, G., & Kern, W. (2005). Approximation theory in combinatorial optimization. Application to the generalized minimum spanning tree problem. Rev. Anal. Numér. Théor. Approx., 34(1), 93–102. https://doi.org/10.33993/jnaat341-795

Issue

Section

Articles