New geometry-inspired relaxations and algorithms for the metric Steiner tree problem
成果类型：
Article
署名作者：
Chakrabarty, Deeparnab; Devanur, Nikhil R.; Vazirani, Vijay V.
署名单位：
University of Waterloo; Microsoft; University System of Georgia; Georgia Institute of Technology
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-009-0299-0
发表日期：
2011
页码：
1-32
关键词：
摘要：
Determining the integrality gap of the bidirected cut relaxation for the metric Steiner tree problem, and exploiting it algorithmically, is a long-standing open problem. We use geometry to define an LP whose dual is equivalent to this relaxation. This opens up the possibility of using the primal-dual schema in a geometric setting for designing an algorithm for this problem. Using this approach, we obtain a 4/3 factor algorithm and integrality gap bound for the case of quasi-bipartite graphs; the previous best integrality gap upper bound being 3/2 (Rajagopalan and Vazirani in On the bidirected cut relaxation for the metric Steiner tree problem, 1999). We also obtain a factor root 2 strongly polynomial algorithm for this class of graphs. A key difficulty experienced by researchers in working with the bidirected cut relaxation was that any reasonable dual growth procedure produces extremely unwieldy dual solutions. A new algorithmic idea helps finesse this difficulty-that of reducing the cost of certain edges and constructing the dual in this altered instance-and this idea can be extracted into a new technique for running the primal-dual schema in the setting of approximation algorithms.