Naslov
An FPTAS for the fractional group Steiner tree problem

Autori
Jelić, Slobodan

Izvornik
Croatian operational research review (1848-0225) 6 (2015), 2; 525-539

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

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

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

Izvorni jezik
Engleski

Znanstvena područja
Računarstvo

POVEZANOST RADA