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

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\).

Keywords

• generalized minimum spanning tree problem