Deterministic risk control for cost-effective network connections

被引：2

作者：

Alvarez-Miranda, Eduardo ^{[2
]}

Chen, Xujin ^{[1
]}

Hu, Jie ^{[3
]}

Hu, Xiaodong ^{[1
]}

Candia-Vejar, Alfredo ^{[2
]}

机构：

[1] Chinese Acad Sci, Inst Appl Math, Beijing 100190, Peoples R China

[2] Univ Talca, Ind Management Dept, Talca, Chile

[3] Beijing Jiaotong Univ, State Key Lab Rail Traff Control & Safety, Beijing 100044, Peoples R China

来源：

THEORETICAL COMPUTER SCIENCE | 2011年 / 412卷 / 03期

关键词：

Polynomial time algorithms; Interval data; Network design; SHORTEST-PATH PROBLEM; SPANNING TREE PROBLEM; INTERVAL DATA; OPTIMIZATION; COMPLEXITY; ALGORITHM;

D O I：

10.1016/j.tcs.2009.08.019

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This paper considers the minimum connection problem in networks with uncertain data. In such a network it is assumed that one can establish a link e by paying a cost c(e) in a given interval [c(e)(-), c(e)(+)] while taking a risk (c(e)(+) - c(e))/(c(e)(+) - c(e)(-)) of link failure. We develop polynomial time algorithms for minimum cost network connection with paths or spanning trees under risk-sum constraints. (C) 2009 Elsevier B.V. All rights reserved.

引用

页码：257 / 264

页数：8

共 11 条

[1] On the complexity of the robust spanning tree problem with interval data [J].

Aron, ID ;

Van Hentenryck, P .

OPERATIONS RESEARCH LETTERS, 2004, 32 (01) :36-40

[2] Interval data minmax regret network optimization problems [J].

Averbakh, I ;

Lebedev, V .

DISCRETE APPLIED MATHEMATICS, 2004, 138 (03) :289-301

[3]

Averbakh I., 2005, Discrete Optimization, V2, P273, DOI DOI 10.1016/J.DISOPT.2005.07.001

[4] Robust discrete optimization and network flows [J].

Bertsimas, D ;

Sim, M .

MATHEMATICAL PROGRAMMING, 2003, 98 (1-3) :49-71

[5] A polynomial solvable minimum risk spanning tree problem with interval data [J].

Chen, Xujin ;

Hu, Jie ;

Hu, Xiaodong .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2009, 198 (01) :43-46

[6] A new model for path planning with interval data [J].

Chen, Xujin ;

Hu, Jie ;

Hu, Xiaodong .

COMPUTERS & OPERATIONS RESEARCH, 2009, 36 (06) :1893-1899

[7]

Karasan O.E., 2001, The robust shortest path problem with interval data

[8]

Kouvelis P., 1997, ROUBUST DISCRETE OPT

[9] An exact algorithm for the robust shortest path problem with interval data [J].

Montemanni, R ;

Gambardella, LM .

COMPUTERS & OPERATIONS RESEARCH, 2004, 31 (10) :1667-1680

[10] A branch and bound algorithm for the robust shortest path problem with interval data [J].

Montemanni, R ;

Gambardella, LM ;

Donati, AV .

OPERATIONS RESEARCH LETTERS, 2004, 32 (03) :225-232

← 1 2 →