{
  "id": "1106.4035",
  "version": "v2",
  "published": "2011-06-20T20:39:33.000Z",
  "updated": "2011-09-27T14:59:33.000Z",
  "title": "Approximation of Geodesics in Metabelian Groups",
  "authors": [
    "O. Kharlampovich",
    "A. Mohajeri Moghaddam"
  ],
  "comment": "10 pages, 1 figure; International Journal of Algebra and Computation (IJAC), 2011",
  "doi": "10.1142/S0218196711006789",
  "categories": [
    "math.GR",
    "math.CO"
  ],
  "abstract": "It is known that the bounded Geodesic Length Problem in free metabelian groups is NP-complete (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 $Z^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 $Z^2$.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2011-09-27T14:59:33.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "20F10",
      "20D10"
    ],
    "keywords": [
      "metabelian groups",
      "geodesic problem",
      "generated non-trivial abelian groups",
      "generated abelian group containing",
      "restricted wreath product"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 10,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1106.4035K"
    }
  }
}