Computer Science – Data Structures and Algorithms
Scientific paper
2010-11-16
Computer Science
Data Structures and Algorithms
26 pages
Scientific paper
We examine directed spanners through flow-based linear programming relaxations. We design an $\~O(n^{2/3})$-approximation algorithm for the directed $k$-spanner problem that works for all $k\geq 1$, which is the first sublinear approximation for arbitrary edge-lengths. Even in the more restricted setting of unit edge-lengths, our algorithm improves over the previous $\~O(n^{1-1/k})$ approximation of Bhattacharyya et al. when $k\ge 4$. For the special case of $k=3$ we design a different algorithm achieving an $\~O(\sqrt{n})$-approximation, improving the previous $\~O(n^{2/3})$. Both of our algorithms easily extend to the fault-tolerant setting, which has recently attracted attention but not from an approximation viewpoint. We also prove a nearly matching integrality gap of $\Omega(n^{\frac13 - \epsilon})$ for any constant $\epsilon > 0$. A virtue of all our algorithms is that they are relatively simple. Technically, we introduce a new yet natural flow-based relaxation, and show how to approximately solve it even when its size is not polynomial. The main challenge is to design a rounding scheme that "coordinates" the choices of flow-paths between the many demand pairs while using few edges overall. We achieve this, roughly speaking, by randomization at the level of vertices.
Dinitz Michael
Krauthgamer Robert
No associations
LandOfFree
Directed Spanners via Flow-Based Linear Programs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Directed Spanners via Flow-Based Linear Programs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Directed Spanners via Flow-Based Linear Programs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-464586