The Common Prefix Problem On Trees

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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.
8 pages

Keywords

Data Structures and Algorithms, Computational Complexity

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/118912

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0612060
 http://arxiv.org/abs/cs/0612060

Collections

arXiv