论文库

Problems in length-constrained network design ask for min-cost subgraphs connecting $k$ input vertex pairs by paths of length at most $h$. Algorithms that instead connect these pairs by paths of length at most $βh$ are said to have length slack $β$. Recent work has shown that poly-time polylogarithmic approximations with polylogarithmic length slack are possible for a broad class of both directed and multicommodity length-constrained network design problems on planar graphs. We give the first poly-time polylogarithmic approximations with $O(1)$ length slack for these problems on planar graphs. In particular, for the length-constrained setting, we give LP-competitive algorithms for planar graphs with length slack $1+ε$ and approximation ratios of $O(\log^2 k/ε)$ for directed Steiner tree and $O(\log^5 k/ε^2)$ for (undirected) Steiner forest. Similarly, for length-constrained directed Steiner forest, we give an $O(\log^6 k/ε)$ approximation on planar graphs with length slack $6+ε$. Our approach is based on a novel charging argument that charges the cost of our solution to the length of the LP and the length of our solution to the cost of the LP. We complement these algorithms with hardness results that separate planar and general graphs for both forest problems: under standard complexity assumptions, we rule out polylogarithmic approximations on general graphs with length slack below $3$.