# A min-max regret approach for the Steiner Tree Problem with Interval Costs

Source: [A min-max regret approach for the Steiner Tree Problem with Interval Costs](<https://www.sota2.com/research/paper/68fa57b21e209131ce9a776f>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T14:52:33.547Z

Authors: Iago A. Carvalho, Amadeu A. Coco, Thiago F. Noronha, Christophe Duhamel

Published: 2021-01-09T12:33:12.000Z

## Abstract

Let G=(V,E) be a connected graph, where V and E represent, respectively, the node-set and the edge-set. Besides, let Q \\subseteq V be a set of terminal nodes, and r \\in Q be the root node of the graph. Given a weight c\_{ij} \\in \\mathbb{N} associated to each edge (i,j) \\in E, the Steiner Tree Problem in graphs (STP) consists in finding a minimum-weight subgraph of G that spans all nodes in Q. In this paper, we consider the Min-max Regret Steiner Tree Problem with Interval Costs (MMR-STP), a robust variant of STP. In this variant, the weight of the edges are not known in advance, but are assumed to vary in the interval \[l\_{ij}, u\_{ij}\]. We develop an ILP formulation, an exact algorithm, and three heuristics for this problem. Computational experiments, performed on generalizations of the classical STP instances, evaluate the efficiency and the limits of the proposed methods.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2101.03347>)

[PDF](<https://arxiv.org/pdf/2101.03347.pdf>)