hrcak mascot   Srce   HID

Izvorni znanstveni članak
https://doi.org/10.17535/crorr.2015.0039

An FPTAS for the fractional group Steiner tree problem

Slobodan Jelić   ORCID icon orcid.org/0000-0002-2134-3112 ; Department of Mathematics, Josip Juraj Strossmayer University of Osijek, Osijek, Hrvatska

Puni tekst: engleski, pdf (123 KB) str. 525-539 preuzimanja: 253* citiraj
APA 6th Edition
Jelić, S. (2015). An FPTAS for the fractional group Steiner tree problem. Croatian Operational Research Review, 6 (2), 525-539. https://doi.org/10.17535/crorr.2015.0039
MLA 8th Edition
Jelić, Slobodan. "An FPTAS for the fractional group Steiner tree problem." Croatian Operational Research Review, vol. 6, br. 2, 2015, str. 525-539. https://doi.org/10.17535/crorr.2015.0039. Citirano 16.09.2019.
Chicago 17th Edition
Jelić, Slobodan. "An FPTAS for the fractional group Steiner tree problem." Croatian Operational Research Review 6, br. 2 (2015): 525-539. https://doi.org/10.17535/crorr.2015.0039
Harvard
Jelić, S. (2015). 'An FPTAS for the fractional group Steiner tree problem', Croatian Operational Research Review, 6(2), str. 525-539. https://doi.org/10.17535/crorr.2015.0039
Vancouver
Jelić S. An FPTAS for the fractional group Steiner tree problem. Croatian Operational Research Review [Internet]. 2015 [pristupljeno 16.09.2019.];6(2):525-539. https://doi.org/10.17535/crorr.2015.0039
IEEE
S. Jelić, "An FPTAS for the fractional group Steiner tree problem", Croatian Operational Research Review, vol.6, br. 2, str. 525-539, 2015. [Online]. https://doi.org/10.17535/crorr.2015.0039

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
https://hrcak.srce.hr/148278

Posjeta: 453 *