An FPTAS for the fractional group Steiner tree problem
Slobodan Jelić · Croatian Operational Research Review · 2015
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.