An FPTAS for the fractional group Steiner tree problem

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...

Full description

Bibliographic Details
Main Author: Slobodan Jelić
Format: Article
Language:English
Published: Croatian Operational Research Society 2015-10-01
Series:Croatian Operational Research Review
Subjects:
approximation algorithm
fully polynomial time approximation scheme
Lagrangean relaxation
group Steiner tree problem
fractional group Steiner tree problem
covering linear program
packing linear program
Online Access:http://hrcak.srce.hr/index.php?show=clanak&id_clanak_jezik=218184

Internet

http://hrcak.srce.hr/index.php?show=clanak&id_clanak_jezik=218184

Similar Items