Name
Title | ||
|---|---|---|
A tabu search algorithm for the minmax regret minimum spanning tree problem with interval data |
Abstract | ||
|---|---|---|
This paper deals with the strongly NP-hard minmax regret version of the minimum spanning tree problem with interval costs. The best known exact algorithms solve the problem in reasonable time for rather small graphs. In this paper an algorithm based on the idea of tabu search is constructed. Some properties of the local minima are shown. Exhaustive computational tests for various classes of graphs are performed. The obtained results suggest that the proposed tabu search algorithm quickly outputs optimal solutions for the smaller instances, previously discussed in the existing literature. Furthermore, some arguments that this algorithm performs well also for larger instances are provided. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/s10732-012-9200-z | J. Heuristics |
Keywords | Field | DocType |
Spanning tree,Minmax regret,Interval data,Tabu search | Minimax,Guided Local Search,Artificial intelligence,Spanning tree,Minimum spanning tree,Mathematical optimization,Regret,Algorithm,Maxima and minima,Interval data,Machine learning,Tabu search,Mathematics | Journal |
Volume | Issue | ISSN |
18 | 4 | 1381-1231 |
Citations | PageRank | References |
9 | 0.58 | 17 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Adam Kasperski | 1 | 352 | 33.64 |
| Mariusz Makuchowski | 2 | 22 | 1.30 |
| Paweł Zieliński | 3 | 274 | 19.73 |