A Factor 3/2 Approximation for Generalized Steiner Tree Problem with Distances One and Two

Simple item page
dc.creatorBerman, Piotr
dc.creatorKarpinski, Marek
dc.creatorZelikovsky, Alex
dc.date2008-12-11
dc.date.accessioned2026-07-07T12:12:00Z
dc.date.available2026-07-07T12:12:00Z
dc.descriptionWe design a 3/2 approximation algorithm for the Generalized Steiner Tree problem (GST) in metrics with distances 1 and 2. This is the first polynomial time approximation algorithm for a wide class of non-geometric metric GST instances with approximation factor below 2.
dc.identifierhttps://arxiv.org/abs/0812.2137
dc.identifierhttp://arxiv.org/abs/0812.2137
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/210403
dc.subjectComputational Complexity
dc.subjectDiscrete Mathematics
dc.subjectData Structures and Algorithms
dc.titleA Factor 3/2 Approximation for Generalized Steiner Tree Problem with Distances One and Two
dc.typetext

Files

Collections

arXiv