.png){kind=icon}
.png){kind=icon}
Return
Simple Approximations for General Spanner Problems
.png){kind=icon}
PRE
AI
DOI：10.1007/978-3-032-06706-7_4.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Consider a (possibly directed) graph with.n nodes and.m edges, independent edge weights and lengths, and arbitrary distance demands for node pairs. The spanner problem asks for a minimum-weight subgraph that satisfies these demands via sufficiently short paths w.r.t. the edge lengths. For multiplicative.a-spanners (where demands equal.a times the original distances) and assuming that each edge's weight equals its length, the simple Greedy heuristic by Althofer et al. (1993) is known to yield strong solutions, both in theory and practice. To obtain guarantees in more general settings, recent approximations typically abandon this simplicity and practicality. Still, so far, there is no known non-trivial approximation algorithm for the spanner problem in its most general form. We provide two surprisingly simple approximations algorithms. In general, our AugmentedGreedy achieves the first unconditional approximation ratio of.m, which is non-trivial due to the independence of weights and lengths. Crucially, it maintains all size and weight guarantees Greedy is known for, i.e., in the aforementioned multiplicative.a-spanner scenario and even for additive.+ss-spanners. Further, it generalizes some of these size guarantees to derive new weight guarantees. Our second approach, RandomizedRounding, establishes a graph transformation that allows a simple rounding scheme over a standard multicommodity flow LP. It yields an.O( n log n)-approximation, assuming integer lengths and polynomially bounded distance demands. The only other known approximation guarantee in this general setting requires several complex subalgorithms and analyses, yet we match it up to a factor of.O(n(1/5- e)) using standard tools. Further, on bounded-degree graphs, we yield the first.O(log n) approximation ratio for constant-bounded distance demands (beyond undirected multiplicative.2-spanners in unitlength graphs).
Keywords:
graph spanners
approximation
linear programming
Journal
A
IF:
0
Papers:
15
Citations:
0