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

共 6 条

[1] Precedence constrained scheduling to minimize sum of weighted completion times on a single machine [J].

Chekuri, C ;

Motwani, R .

DISCRETE APPLIED MATHEMATICS, 1999, 98 (1-2) :29-38

[2] A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine [J].

Chudak, FA ;

Hochbaum, DS .

OPERATIONS RESEARCH LETTERS, 1999, 25 (05) :199-204

[3]

Graham R. L., 1979, Discrete Optimisation, P287

[4] Scheduling to minimize average completion time: Off-line and on-line approximation algorithms [J].

Hall, LA ;

Schulz, AS ;

Shmoys, DB ;

Wein, J .

MATHEMATICS OF OPERATIONS RESEARCH, 1997, 22 (03) :513-544

[5]

PISARUK NI, 1992, COMP MATH MATH PHYS+, V32, P1769

[6] A fully combinatorial 2-approximation algorithm for precedence-constrained scheduling a single machine to minimize average weighted completion time [J].

Pisaruk, NN .

DISCRETE APPLIED MATHEMATICS, 2003, 131 (03) :655-663

← 1 →