On an Optimal Split Tree Problem
On an Optimal Split Tree Problem
复制标题
关于最优分裂树问题
DOI：
10.1007/3-540-48447-7_17
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
R. Borgstrom
中科院分区：
文献类型：
--
作者：
S. R. Kosaraju;T. Przytycka;R. Borgstrom
我们介绍并研究了一个我们称之为最优分割树问题的问题。该问题推广了许多问题，包括两个经典的树构造问题，即Huffman树问题和最优字母树问题。我们证明了一般的分裂树问题是np完全的，并分析了其解的贪心算法。我们证明了贪婪算法的一个简单修改保证了O（log n）的近似比。我们构造了一个例子，该算法实现Ω（log n/log log n）近似比。我们证明了如果所有权值相等且最优分割树深度为O(log n)，那么贪婪算法保证了O（log n/log log n）近似比。我们还将逼近算法扩展到构造部分有序集的搜索树。
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 Ω(log n/log log n) 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(log n/log log n) approximation ratio. We also extend our approximation algorithm to the construction of a search tree for partially ordered sets.