文章基本信息

标题：A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs
本地全文：下载
作者：Zachary Friggstad ; Jochen K{\"o}nemann ; Mohammad Shadravan 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：53
页码：3:1-3:11
DOI：10.4230/LIPIcs.SWAT.2016.3
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We demonstrate that the integrality gap of the natural cut-based LP relaxation for the directed Steiner tree problem is O(log k) in quasi-bipartite graphs with k terminals. Such instances can be seen to generalize set cover, so the integrality gap analysis is tight up to a constant factor. A novel aspect of our approach is that we use the primal-dual method; a technique that is rarely used in designing approximation algorithms for network design problems in directed graphs.
关键词：Approximation algorithm; Primal-Dual algorithm; Directed Steiner tree