This work studies the problem of finding optimal paths with respect to the center, median and centdian objective functions, on networks with uncertain vertex weights that are given as intervals. Our approach looks for minimax regret paths which minimize the worst-case opportunity loss in the corresponding objective function. These problems are NP-hard on general graphs, therefore we study them on trees. We show that a discrete optimal path always exists for each of them, and provide polynomial time solution algorithms. (C) 2011 Wiley Periodicals, Inc. NETWORKS, Vol. 58(2), 147-158 2011
Minimax Regret Path Location on Trees / Justo, Puerto; Ricca, Federica; Andrea, Scozzari. - In: NETWORKS. - ISSN 0028-3045. - STAMPA. - 58:2(2011), pp. 147-158. (Intervento presentato al convegno Graphs and Optimization Meeting tenutosi a Saint Maximim La Sainte Ba, FRANCE nel AUG 24-27, 2008) [10.1002/net.20453].
Minimax Regret Path Location on Trees
RICCA, Federica;
2011
Abstract
This work studies the problem of finding optimal paths with respect to the center, median and centdian objective functions, on networks with uncertain vertex weights that are given as intervals. Our approach looks for minimax regret paths which minimize the worst-case opportunity loss in the corresponding objective function. These problems are NP-hard on general graphs, therefore we study them on trees. We show that a discrete optimal path always exists for each of them, and provide polynomial time solution algorithms. (C) 2011 Wiley Periodicals, Inc. NETWORKS, Vol. 58(2), 147-158 2011I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
