Approximation of Geodesics in Metabelian Groups

Olga Kharlampovich, CUNY Hunter College

Abstract: We study the geodesic problem in the restricted wreath product of a finitely generated group with a finitely generated abelian group containing Z^2. We prove that the geodesic problem is NP-hard in this case. In the second part we show that there exists a Polynomial Time Approximation Scheme for this problem. Existence of a 2-approximation polynomial algorithm for the geodesic problem in free metabelian groups will be shown in the third part. Joint with Atefeh Mohajeri (McGill).