Approximation theory in combinatorial optimization. Application to the generalized minimum spanning tree problem
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 t...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Publishing House of the Romanian Academy
2005-02-01
|
| Series: | Journal of Numerical Analysis and Approximation Theory |
| Subjects: | |
| Online Access: | https://www.ictp.acad.ro/jnaat/journal/article/view/795 |
| Summary: | 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\). |
|---|---|
| ISSN: | 2457-6794 2501-059X |