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(TK) {Sigma(e is an element of TK) c(e) + k(T-K) . 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 3/2-approximation algorithm to solve the special case for constant construction cost of edges. (3) An APTAS for this special case.