An FPTAS for the fractional group Steiner tree problem

Slobodan Jelić

Abstract


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\varepsilon$ times the optimal, for $\varepsilon\in\langle0,1/6]$, in $\tilde{O(mk(m+n^{4/3}\varepsilon^{-16/3})/\varepsilon^2)$ time, where $n$, $m$ and $k$ are 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.


Full Text:

PDF

Refbacks

  • There are currently no refbacks.


ISSN: 1848-0225 Print, ISSN 1848-9931 Online, Publisher: Croatian Operational Research Society, Trg J.F. Kenneddyja 6, 10000 Zagreb, Croatia, e-mail: hdoi@hdoi.hr, Co-publishers: University of Osijek, Faculty of Economics in Osijek; University of Osijek, Department of Mathematics; University of Split, Faculty of Economics; University of Zagreb, Faculty of Economics and Business