Approximation algorithms for constructing spanning K-trees using stock pieces of bounded length
| Autor: | Junran Lichen, Jianping Li, Ko-Wei Lih |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Discrete mathematics
021103 operations research Control and Optimization Spanning tree 0211 other engineering and technologies Minimum weight Approximation algorithm 0102 computer and information sciences 02 engineering and technology 01 natural sciences Graph Combinatorics 010201 computation theory & mathematics Bounded function K-tree Sale price Mathematics |
| Zdroj: | Optimization Letters. 11:1663-1675 |
| ISSN: | 1862-4480 1862-4472 |
| DOI: | 10.1007/s11590-016-1078-5 |
| Popis: | Given a weighted graph G on $$n + 1$$ vertices, a spanning K-tree $$T_K$$ of G is defined to be a spanning tree T of G together with K distinct edges of G that are not edges of T. The objective of the minimum-cost spanning K-tree problem is to choose a subset of edges to form a spanning K-tree with the minimum weight. In this paper, we consider the constructing spanning K-tree problem that is a generalization of the minimum-cost spanning K-tree problem. We are required to construct a spanning K-tree $$T_K$$ whose $$n+K$$ edges are assembled from some stock pieces of bounded length L. Let $$c_0$$ be the sale price of each stock piece of length L and $$k(T_K)$$ the number of minimum stock pieces to construct the $$n+K$$ edges in $$T_K$$ . For each edge e in G, let c(e) be the construction cost of that edge e. Our new objective is to minimize the total cost of constructing a spanning K-tree $$T_K$$ , i.e., $$\min _{T_K}\{\sum _{e\in T_K} c(e)+ k(T_K)\cdot c_0\}$$ . The main results obtained in this paper are as follows. (1) A 2-approximation algorithm to solve the constructing spanning K-tree problem. (2) A $$\frac{3}{2}$$ -approximation algorithm to solve the special case for constant construction cost of edges. (3) An APTAS for this special case. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink