Interval data minmax regret network optimization problems

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.