Minimizing Maximum Risk for Fair Network Connection with Interval Data  

作　　者：Jie Hu 

机构地区：[1]State Key Laboratory of Rail Traffic Control and Safety, Beijing Jiaotong University, Beijing 100044, China

出　　处：《Acta Mathematicae Applicatae Sinica》2010年第1期33-40,共8页应用数学学报（英文版）

基　　金：Supported by the National Natural Science Foundation of China(No.10531070,10771209,10721101,70631001);Chinese Academy of Sciences under Grant No.kjcx-yw-s7

摘　　要：In this paper we introduce a minimax model for network connection problems with interval parameters. We consider how to connect given nodes in a network with a path or a spanning tree under a given budget, where each link is associated with an interval and can be established at a cost of any value in the interval. The quality of an individual link （or the risk of link failure, etc.） depends on its construction cost and associated interval. To achieve fairness of the network connection, our model aims at the minimization of the maximum risk over all links used. We propose two algorithms that find optimal paths and spanning trees in polynomial time, respectively. The polynomial solvability indicates salient difference between our minimax model and the model of robust deviation criterion for network connection with interval data, which gives rise to NP-hard optimization problems.In this paper we introduce a minimax model for network connection problems with interval parameters. We consider how to connect given nodes in a network with a path or a spanning tree under a given budget, where each link is associated with an interval and can be established at a cost of any value in the interval. The quality of an individual link （or the risk of link failure, etc.） depends on its construction cost and associated interval. To achieve fairness of the network connection, our model aims at the minimization of the maximum risk over all links used. We propose two algorithms that find optimal paths and spanning trees in polynomial time, respectively. The polynomial solvability indicates salient difference between our minimax model and the model of robust deviation criterion for network connection with interval data, which gives rise to NP-hard optimization problems.

关 键 词：Network connection interval data shortest path spanning tree minimax approach 

分 类 号：TP393[自动化与计算机技术—计算机应用技术] TP311.13[自动化与计算机技术—计算机科学与技术]