Network Designs: Approximations for Steiner Minimum Trees

Ding-Zhu Du

ABSTRACT

The Steiner tree is a typical optimization problem in network designs. Study of Steiner tree problems received great attention in the 1990s since many important open problems, including the Gilbert-Pollak conjecture on the Euclidean Steiner ratio, the existence of better approximation, and the existence of the polynomial-time approximation scheme, were solved, which influenced the general theory of designs and analysis of approximation algorithms for combinatorial optimizations. In this survey, we follow those recent developments to review results regarding the approximation of Steiner minimum trees and related problems. Throughout this review, we summarize and propose open problems to encourage research work in this direction.