### Minimax regret spanning arborescences under uncertain costs

### Abstract

The paper considers a classical optimization problem on a network whose arc costs are partially known. It is assumed that an interval estimate is given for each arc cost and no further information about the statistical distribution of the truth value of the arc cost is known. In this context, given a spanning arborescence in the network, its cost can take on different values according to the choice of each individual arc cost, that is, according to the different cost scenarios. We analyze the problem of finding which spanning arborescence better approaches the optimal one under each possible scenario. The minimax regret criterion is proposed in order to obtain such a robust solution to the problem. In the paper, it is shown that a greedy-type algorithm can compute an optimal solution of this problem on acyclic networks. For general networks, the problem becomes NP-hard. In this case, the special structure of the optimization problem allows us to design a bounding process for the optimum value that will result in a heuristic algorithm described at the end of the paper. Â© 2006 Elsevier B.V. All rights reserved.

### Más información

Título según WOS: | Minimax regret spanning arborescences under uncertain costs |

Título según SCOPUS: | Minimax regret spanning arborescences under uncertain costs |

Título de la Revista: | EUROPEAN JOURNAL OF OPERATIONAL RESEARCH |

Volumen: | 182 |

Número: | 2 |

Editorial: | Elsevier |

Fecha de publicación: | 2007 |

Página de inicio: | 561 |

Página final: | 577 |

Idioma: | English |

URL: | http://linkinghub.elsevier.com/retrieve/pii/S0377221706008484 |

DOI: |
10.1016/j.ejor.2006.07.036 |

Notas: | ISI, SCOPUS |