Worst-case performance of Wong's Steiner tree heuristic

Candia-Vejar, A. Department of Systems Engineering, Universidad de Talca, Merced 437, Curicó, Chile.A study of the worst-case performance of Wong's heuristic for the Steiner problem in directed networks (SPDN) is presented in this paper. SPDN is a classic combinatorial optimization problem having the status of a very difficult problem (-hard problem) and it is known as an optimization model for a broad class of problems in networks. Several exact and heuristic approaches have been designed for SPDN in the last twenty five years. Some papers analyze theoretical and experimental behavior of heuristics for SPDN, specially for undirected networks, but none of these has studied the worst-case performance of Wong's heuristic. In this paper, we find a lower bound for that performance and show that this bound is consistent with comparable results in the literature on SPDN and its undirected version