期刊
DISCRETE APPLIED MATHEMATICS
卷 138, 期 3, 页码 289-301出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/S0166-218X(03)00462-1
关键词
minmax regret optimization; spanning tree; shortest path
We consider the minimum spanning tree and the shortest path problems on a network with uncertain lengths of edges. In particular, for any edge of the network, only an interval estimate of the length of the edge is known, and it is assumed that the length of each edge can take on any value from the corresponding interval of uncertainty, regardless of the values taken by the lengths of other edges. It is required to find a minmax regret solution. We prove that both problems are NP-hard even if the bounds of all intervals of uncertainty belong to {0, 1}. The interval data minmax regret shortest path problem is NP-hard even if the network is directed, acyclic, and has a layered structure. We show that the problems are polynomially solvable in the practically important case where the number of edges with uncertain lengths is fixed or is bounded by the logarithm of a polynomial function of the total number of edges. We discuss implications of these results for the general theory of interval data minmax regret combinatorial optimization. (C) 2003 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据