Naslov
On the fractional group Steiner tree problem

Autori
Jelić ; Slobodan

Vrsta, podvrsta i kategorija rada
Sažeci sa skupova, sažetak, znanstveni

Izvornik
XLII International Symposiumon Operational Research / - , 2015, 315-318

Skup
XLII International Symposium on Operational Research

Mjesto i datum
Veliko Gradište, Srbija, 15.09.2015. - 18.09.2015

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Recenziran

Ključne riječi
fully polynomial time approximation scheme, 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 an approach of Koufogiannakis and Young (2013) with nearly-linear time approximation scheme for minimum cut problem in Christiano et. al (2011) in order to develop a fully polynomial time approximation scheme for FGST problem. Our algorithm returns the solution to FGST whose objective function value is at most 1+6ε times optimal, for ε∈(0, 1/6], in polynomial time with respect to n, m, and k, where n, m and k are numbers of nodes, edges and groups in the group Steiner tree instance, respectively. This algorithm has a better worst-case running time than the previous one in Garg and Khandekar (2002) when the number of groups is large enough.

Izvorni jezik
Engleski

Znanstvena područja
Matematika, Računarstvo

POVEZANOST RADA