A 2-approximation algorithm for the network substitution problem

被引：0
|
作者：
Pisaruk, NN [1 ]
机构：
[1] Belarusian State Univ, Fac Appl Math & Informat, Minsk 220088, BELARUS
来源：
OPERATIONS RESEARCH LETTERS | 2006年 / 34卷 / 01期
关键词：
network; scheduling; complexity; approximation algorithm;
D O I：
10.1016/j.orl.2005.03.005
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
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. (c) 2005 Elsevier B.V. All rights reserved.
引用
收藏
页码：94 / 96
页数：3
相关论文
共 50 条
  • [1] A fast 2-approximation algorithm for the Minimum Manhattan Network problem
    Guo, Zeyu
    Sun, He
    Zhu, Hong
    ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, PROCEEDINGS, 2008, 5034 : 212 - +
  • [2] A 2-approximation polynomial algorithm for a clustering problem
    Kel'manov A.V.
    Khandeev V.I.
    Kel'manov, A. V. (kelm@math.nsc.ru), 1600, Izdatel'stvo Nauka (07): : 515 - 521
  • [3] A 2-approximation algorithm for the zookeeper's problem
    Tan, Xuehou
    INFORMATION PROCESSING LETTERS, 2006, 100 (05) : 183 - 187
  • [4] A 2-approximation algorithm for the directed multiway cut problem
    Naor, JS
    Zosin, L
    SIAM JOURNAL ON COMPUTING, 2001, 31 (02) : 477 - 482
  • [5] A 2-approximation algorithm for the directed multiway cut problem
    Naor, JS
    Zosin, L
    38TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1997, : 548 - 553
  • [6] A 2-Approximation Algorithm for the Online Tethered Coverage Problem
    Sharma, Gokarna
    Poudel, Pavan
    Dutta, Ayan
    Zeinali, Vala
    Khoei, Tala Talaei
    Kim, Jong-Hoon
    ROBOTICS: SCIENCE AND SYSTEMS XV, 2019,
  • [7] A 3/2-approximation algorithm for the mixed postman problem
    Raghavachari, B
    Veerasamy, J
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 1999, 12 (04) : 425 - 433
  • [8] A Local 2-Approximation Algorithm for the Vertex Cover Problem
    Astrand, Matti
    Floreen, Patrik
    Polishchuk, Valentin
    Rybicki, Joel
    Suomela, Jukka
    Uitto, Jara
    DISTRIBUTED COMPUTING, PROCEEDINGS, 2009, 5805 : 191 - 205
  • [9] A 2-Approximation Algorithm for the Graph 2-Clustering Problem
    Il'ev, Victor
    Il'eva, Svetlana
    Morshinin, Alexander
    MATHEMATICAL OPTIMIZATION THEORY AND OPERATIONS RESEARCH, 2019, 11548 : 295 - 308
  • [10] A 2-approximation algorithm for the undirected feedback vertex set problem
    Bafna, V
    Berman, P
    Fujito, T
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 1999, 12 (03) : 289 - 297
12345