| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 6874141 | Information Processing Letters | 2018 | 15 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Junran Lichen, Jianping Li, Ko-Wei Lih,