Heuristics for the central tree problem

被引：0
作者：
Jørgen Bang-Jensen
Yury Nikulin
机构：
[1] University of Southern Denmark,Department of Mathematics and Computer Science
[2] University of Turku,Department of Mathematics
来源：
Journal of Heuristics | 2010年 / 16卷
关键词：
Minmax regret; Robustness; Central tree; Spanning tree; Local search;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
This paper addresses the central spanning tree problem (CTP). The problem consists in finding a spanning tree that minimizes the so-called robust deviation, i.e. deviation from a maximally distant tree. The distance between two trees is measured by means of the symmetric difference of their edge sets. The central tree problem is known to be NP-hard. We attack the problem with a hybrid heuristic consisting of: (1) a greedy construction heuristic to get a good initial solution and (2) fast local search improvement. We illustrate computationally efficiency of the proposed approach.
引用
收藏
页码：633 / 651
页数：18
相关论文
共 26 条
  • [1] Amoia A.(1971)Invariance properties of central trees IEEE Trans. Circuit Theory CT 18 465-467
  • [2] Cottafava G.(2004)On the complexity of the robust spanning tree problem with interval data Oper. Res. Lett. 32 36-40
  • [3] Aron I.(2004)Interval data regret network optimization problems Discrete Appl. Math. 138 289-301
  • [4] van Hentenryck P.(1996)On central spanning trees of a graph Lect. Notes Comput. Sci. 1120 53-58
  • [5] Averbakh I.(1966)A central tree IEEE Trans. Circuit Theory CT 13 439-440
  • [6] Lebedev V.(2006)An approximation algorithm for interval data minmax regret combinatorial optimization problems Inf. Process. Lett. 97 177-180
  • [7] Bezrukov S.(1969)Maximally distant trees and principal partition of a linear graph IEEE Trans. Circuit Theory CT 16 323-330
  • [8] Kaderali F.(1994)Interval spanning tree problem: solvability and computational complexity Interval Comput. 1 42-50
  • [9] Poguntke W.(2006)A Benders decomposition approach for the robust spanning tree problem with interval data Eur. J. Oper. Res. 174 1479-1490
  • [10] Deo N.(2005)A branch and bound algorithm for the robust spanning tree problem with interval data Eur. J. Oper. Res. 161 771-779
123