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 2011
2011
efficient algorithms; minimax regret optimization; path location
01 Pubblicazione su rivista::01a Articolo in rivista
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].
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/377944
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 14
  • ???jsp.display-item.citation.isi??? 13
social impact