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 |
| _version_ | 1818520935049723904 |
|---|---|
| author | Petrică C. Pop G. Still W. Kern |
| author_facet | Petrică C. Pop G. Still W. Kern |
| author_sort | Petrică C. Pop |
| collection | DOAJ |
| description | 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\). |
| first_indexed | 2024-12-11T01:44:18Z |
| format | Article |
| id | doaj.art-a1c6d192cdce478496451c39439d45bd |
| institution | Directory Open Access Journal |
| issn | 2457-6794 2501-059X |
| language | English |
| last_indexed | 2024-12-11T01:44:18Z |
| publishDate | 2005-02-01 |
| publisher | Publishing House of the Romanian Academy |
| record_format | Article |
| series | Journal of Numerical Analysis and Approximation Theory |
| spelling | doaj.art-a1c6d192cdce478496451c39439d45bd2022-12-22T01:24:56ZengPublishing House of the Romanian AcademyJournal of Numerical Analysis and Approximation Theory2457-67942501-059X2005-02-01341Approximation theory in combinatorial optimization. Application to the generalized minimum spanning tree problemPetrică C. Pop0G. Still1W. Kern2North University of Baia Mare, RomaniaUniversity of Twente, NetherlandsUniversity of Twente, NetherlandsWe 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\).https://www.ictp.acad.ro/jnaat/journal/article/view/795generalized minimum spanning tree problem |
| spellingShingle | Petrică C. Pop G. Still W. Kern Approximation theory in combinatorial optimization. Application to the generalized minimum spanning tree problem Journal of Numerical Analysis and Approximation Theory generalized minimum spanning tree problem |
| title | Approximation theory in combinatorial optimization. Application to the generalized minimum spanning tree problem |
| title_full | Approximation theory in combinatorial optimization. Application to the generalized minimum spanning tree problem |
| title_fullStr | Approximation theory in combinatorial optimization. Application to the generalized minimum spanning tree problem |
| title_full_unstemmed | Approximation theory in combinatorial optimization. Application to the generalized minimum spanning tree problem |
| title_short | Approximation theory in combinatorial optimization. Application to the generalized minimum spanning tree problem |
| title_sort | approximation theory in combinatorial optimization application to the generalized minimum spanning tree problem |
| topic | generalized minimum spanning tree problem |
| url | https://www.ictp.acad.ro/jnaat/journal/article/view/795 |
| work_keys_str_mv | AT petricacpop approximationtheoryincombinatorialoptimizationapplicationtothegeneralizedminimumspanningtreeproblem AT gstill approximationtheoryincombinatorialoptimizationapplicationtothegeneralizedminimumspanningtreeproblem AT wkern approximationtheoryincombinatorialoptimizationapplicationtothegeneralizedminimumspanningtreeproblem |