Abstract
We introduce and study a problem that we refer to as the optimal split tree problem. The problem generalizes a number of problems including two classical tree construction problems including the Huffman tree problem and the optimal alphabetic tree. We show that the general split tree problem is NP-complete and analyze a greedy algorithm for its solution. We show that a simple modification of the greedy algorithm guarantees O(log n) approximation ratio. We construct an example for which this algorithm achieves Ω \( \Omega \left( {\frac{{\log n}} {{\log \log n}}} \right) \) approximation ratio. We show that if all weights are equal and the optimal split tree is of depth O(log n), then the greedy algorithm guarantees O \( \Omega \left( {\frac{{\log n}} {{\log \log n}}} \right) \) approximation ratio. We also extend our approximation algorithm to the construction of a search tree for partially ordered sets.
Research supported by NSF grant CCR9508545 and ARO grant DAAH04-96-1-0013.
Research supported by the Sloan and Department of Energy Postdoctoral Fellowship for Computational Biology.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J. Abrahams, Private Communication. DIMACS 1998.
J. Abrahams, DIMACS Workshop on Codes and Trees. October 1998.
T. M. Cover, J.A. Thomas, Elements of Information Theory. John Wiley & Sons. Inc., New York. 1991.
A. Itai, Optimal alphabetic trees. SIAM Journal of Computing 5 (1976) pp.9–18.
A. M. Garsia and M. L. Wachs, A New algorithm for minimal binary search trees. SIAM Journal of Computing 6 (1977) pp. 622–642.
M. R. Garey, Optimal binary search trees with restricted maximal depth. SIAM Journal of Computing 3 (1974) pp.101–110.
J. H. Kingston, A new proof of the Garsia-Wachs algorithm. Journal of Algorithms 9 (1998) 129–138.
T. C. Hu and A. C. Tucker, Optimal computer search trees and variable length alphabetic codes. SIAM Journal of Applied Mathematics 21 (1971) pp. 514–532.
D. A. Huffman, A Method for the construction of minimum redundancy codes. Proceedings of the Institute of Radio Engineers 40 (1952) pp.1098–1101.
L. L. Larmore, Height restricted optimal alphabetic trees. SIAM Journal of Computing 16 (1987) pp. 1115–1123.
L.L. Larmore, T. Przytycka, Optimal alphabetic tree problem revisited. Journal of Algorithms 28 pp.1–20 extended abstract published in ICALP’ 94, LNCS 820, Springer-Verlag, pp 251-262
L.L. Larmore, T. Przytycka, A Fast Algorithm for Optimum Height Limited Alphabetic Binary Trees. SIAM Journal on Computing 23 pp.1283–1312.
R.M. Karp, Reducibility among combinatorial problems. in R.E. Miller and J.W. Teatcher. eds. Complexity of Computer Computations Plenum Press. New York, 85–103, 1972.
D. E. Knuth, Optimum binary search trees. Acta Informatica 1 pp.14–25.
R. L. Wessner, Optimal alphabetic search trees with restricted maximal height. Information Processing Letters 4 pp.90–94.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kosaraju, S.R., Przytycka, T.M., Borgstrom, R. (1999). On an Optimal Split Tree Problem. In: Dehne, F., Sack, JR., Gupta, A., Tamassia, R. (eds) Algorithms and Data Structures. WADS 1999. Lecture Notes in Computer Science, vol 1663. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48447-7_17
Download citation
DOI: https://doi.org/10.1007/3-540-48447-7_17
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66279-2
Online ISBN: 978-3-540-48447-9
eBook Packages: Springer Book Archive