The Common Prefix Problem On Trees
<|reference_start|>The Common Prefix Problem On Trees: We present a theoretical study of a problem arising in database query optimization, which we call as The Common Prefix Problem. We present a $(1-o(1))$ factor approximation algorithm for this problem, when the underlying graph is a binary tree. We then use a result of Feige and Kogan to show that even on stars, the problem is hard to approximate.<|reference_end|>
@article{kenkre2006the,
    title={The Common Prefix Problem On Trees},
    author={Sreyash Kenkre, Sundar Vishwanathan},
    journal={arXiv preprint arXiv:cs/0612060},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0612060},
    primaryClass={cs.DS cs.CC}
}