We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
APPROXIMATION OF GEODESICS IN METABELIAN GROUPS.
- Authors
KHARLAMPOVICH, OLGA; MOHAJERI MOGHADDAM, ATEFEH; Sapir, Mark
- Abstract
It is known that the bounded Geodesic Length Problem in free metabelian groups is NP-complete [A. Myasnikov, V. Roman'kov, A. Ushakov and A. Vershik, The word and geodesic problems in free solvable groups, Trans. Amer. Math. Soc.362(9) (2010) 4655-4682] (in particular, the Geodesic Problem is NP-hard). We construct a 2-approximation polynomial time deterministic algorithm for the Geodesic Problem. We show that the Geodesic Problem in the restricted wreath product of a finitely generated non-trivial group with a finitely generated abelian group containing ℤ2 is NP-hard and there exists a Polynomial Time Approximation Scheme for this problem. We also show that the Geodesic Problem in the restricted wreath product of two finitely generated non-trivial abelian groups is NP-hard if and only if the second abelian group contains ℤ2.
- Subjects
GEODESICS; FREE metabelian groups; APPROXIMATION theory; POLYNOMIALS; ALGORITHMS; ABELIAN groups; PROBLEM solving
- Publication
International Journal of Algebra & Computation, 2012, Vol 22, Issue 2, p1250012
- ISSN
0218-1967
- Publication type
Article
- DOI
10.1142/S0218196711006789