Izvorni znanstveni članak
https://doi.org/10.17535/crorr.2015.0039
An FPTAS for the fractional group Steiner tree problem
Slobodan Jelić
orcid.org/0000-0002-2134-3112
; Odjel za matematiku, Sveučilište Josipa Jurja Strossmayera u Osijeku, Osijek, Hrvatska
Sažetak
This paper considers a linear relaxation of the cut-based integer programming formulation for the group Steiner tree problem (FGST). We combine the approach of Koufogiannakis and Young (2013) with the nearly-linear time approximation scheme for the minimum cut problem of Christiano et. al (2011) in order to develop a fully polynomial time approximation scheme for FGST problem. Our algorithm returns the solution to FGST where the objective function value is a maximum of 1+6ε times the optimal, for ε ∈〈0;1/6] in Õ(mk(m+n^4/3 ε^–16/3)/ε^2) time, where n, m and k are the numbers of vertices, edges and groups in the group Steiner tree instance, respectively. This algorithm has a better worst-case running time than algorithm by Garg and Khandekar (2002) where the number of groups is sufficiently large.
Ključne riječi
approximation algorithm; fully polynomial time approximation scheme; Lagrangean relaxation; group Steiner tree problem; fractional group Steiner tree problem, covering linear program; packing linear program
Hrčak ID:
148278
URI
Datum izdavanja:
31.10.2015.
Posjeta: 1.294 *