2026-07-072026-07-07http://salesiana.dossiersoluciones.com/handle/123456789/118912We 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 pagesData Structures and AlgorithmsComputational Complexitytext