Name
Abstract | ||
|---|---|---|
This paper studies a 4-approximation algorithm for k-prize collecting Steiner tree problems. This problem generalizes both k-minimum spanning tree problems and prize collecting Steiner tree problems. Our proposed algorithm employs two 2-approximation algorithms for k-minimum spanning tree problems and prize collecting Steiner tree problems. Also our algorithm framework can be applied to a special case of k-prize collecting traveling salesman problems. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/s11590-018-1367-2 | OPTIMIZATION LETTERS |
Keywords | Field | DocType |
Approximation algorithm,Primal-dual algorithm,k-prize collecting Steiner tree problems,k-prize collecting traveling salesman problems | Approximation algorithm,Discrete mathematics,Mathematical optimization,Steiner tree problem,Travelling salesman problem,Spanning tree,Mathematics,Special case | Journal |
Volume | Issue | ISSN |
13.0 | 2.0 | 1862-4472 |
Citations | PageRank | References |
1 | 0.36 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yusa Matsuda | 1 | 1 | 0.36 |
| Satoshi Takahashi | 2 | 2 | 4.09 |