An FPTAS for the fractional group Steiner tree problem
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...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Croatian Operational Research Society
2015-10-01
|
| Series: | Croatian Operational Research Review |
| Subjects: | |
| Online Access: | http://hrcak.srce.hr/index.php?show=clanak&id_clanak_jezik=218184 |
| _version_ | 1818251215443591168 |
|---|---|
| author | Slobodan Jelić |
| author_facet | Slobodan Jelić |
| author_sort | Slobodan Jelić |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-12T16:04:44Z |
| format | Article |
| id | doaj.art-4440cc79bccf4382a1ecf00947c7210f |
| institution | Directory Open Access Journal |
| issn | 1848-0225 1848-9931 |
| language | English |
| last_indexed | 2024-12-12T16:04:44Z |
| publishDate | 2015-10-01 |
| publisher | Croatian Operational Research Society |
| record_format | Article |
| series | Croatian Operational Research Review |
| spelling | doaj.art-4440cc79bccf4382a1ecf00947c7210f2022-12-22T00:19:20ZengCroatian Operational Research SocietyCroatian Operational Research Review1848-02251848-99312015-10-016252553910.17535/crorr.2015.0039An FPTAS for the fractional group Steiner tree problemSlobodan Jelić0Department of Mathematics, Josip Juraj Strossmayer University of Osijek, Osijek, HrvatskaThis 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.http://hrcak.srce.hr/index.php?show=clanak&id_clanak_jezik=218184approximation algorithmfully polynomial time approximation schemeLagrangean relaxationgroup Steiner tree problemfractional group Steiner tree problemcovering linear programpacking linear program |
| spellingShingle | Slobodan Jelić An FPTAS for the fractional group Steiner tree problem Croatian Operational Research Review approximation algorithm fully polynomial time approximation scheme Lagrangean relaxation group Steiner tree problem fractional group Steiner tree problem covering linear program packing linear program |
| title | An FPTAS for the fractional group Steiner tree problem |
| title_full | An FPTAS for the fractional group Steiner tree problem |
| title_fullStr | An FPTAS for the fractional group Steiner tree problem |
| title_full_unstemmed | An FPTAS for the fractional group Steiner tree problem |
| title_short | An FPTAS for the fractional group Steiner tree problem |
| title_sort | fptas for the fractional group steiner tree problem |
| topic | approximation algorithm fully polynomial time approximation scheme Lagrangean relaxation group Steiner tree problem fractional group Steiner tree problem covering linear program packing linear program |
| url | http://hrcak.srce.hr/index.php?show=clanak&id_clanak_jezik=218184 |
| work_keys_str_mv | AT slobodanjelic anfptasforthefractionalgroupsteinertreeproblem AT slobodanjelic fptasforthefractionalgroupsteinertreeproblem |