Approximation algorithms for constructing spanning K-trees using stock pieces of bounded length

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.