A 2-approximation algorithm for the network substitution problem |
| |
| Authors: | Nicolai N. Pisaruk |
| |
| Affiliation: | Faculty of Applied Mathematics and Informatics, Belarus State University, F. Skarina Av. 4, 220088 Minsk, Belarus |
| |
| Abstract: | The network substitution problem is to substitute an existing network for a new network so that to minimize the cost of exploiting the existing network during the period when the new network is being constructed. We show that this problem is NP-hard, and propose a 2-approximation algorithm for solving it. |
| |
| Keywords: | Network Scheduling Complexity Approximation algorithm |
| 本文献已被 ScienceDirect 等数据库收录！ |
