Approximation algorithms for constructing specific subgraphs with minimum number of length-bounded stock pieces

We obtain two main results. (1) Whenever the CSS problem Q can be approximated by an α-approximation algorithm (α≥1) (for the case α=1, the CSS problem Q is solved optimally by a polynomial-time exact algorithm), we design two approximation algorithms with performance ratios 2α and 7α4 to solve the CSS-MSP problem Q′; (2) In addition, when the problem Q is to find a minimum spanning tree, we present a 32-approximation algorithm and an APTAS to solve the problem Q′ of constructing spanning tree with minimum number of length-bounded stock pieces.