The genomes of many species are dominated by short sequences repeated consecutively called tandem repeats. An understanding of the biological mechanisms that create and extend tandem repeats would be facilitated by reconstructing the history of duplication events that generated the tandem repeats. This paper explores the computational problem of reconstructing the duplication history of a tandem repeat. Specifically, the problem of reconstructing the minimum-cost duplication history is proved to be NP-hard even if the lengths and boundaries for the duplication events are fixed. When the lengths and boundaries are fixed, the minimum-cost duplication history can actually be represented by a tree. A nontrivial extension of the tree-alignment algorithms from [Wang et al. (Algorithmica 16 (1996) 302; SIAM J. Comput. 30 (1) (2000) 283)] gives a polynomial time approximation scheme (PTAS) for this special case. Experiments on more than 9000 tandem repeats from human chromosomes 1 and 22 demonstrate that our PTAS generates less costly histories in acceptable time than other heuristic methods. We also note that our PTAS works for any metric space. Therefore, our algorithm is also a PTAS for constructing a minimum Steiner tree (MST) when the order of all the regular nodes on the output Steiner tree is known.