Name
Abstract | ||
|---|---|---|
We show that the shortest-path metric of any $k$-outerplanar graph, for any fixed $k$, can be approximated by a probability distribution over tree metrics with constant distortion and hence also embedded into $\ell_1$ with constant distortion. These graphs play a central role in polynomial time approximation schemes for many NP-hard optimization problems on general planar graphs and include the family of weighted $k\times n$ planar grids. This result implies a constant upper bound on the ratio between the sparsest cut and the maximum concurrent flow in multicommodity networks for $k$-outerplanar graphs, thus extending a theorem of Okamura and Seymour [J. Combin. Theory Ser. B, 31 (1981), pp. 75-81] for outerplanar graphs, and a result of Gupta et al. [Combinatorica, 24 (2004), pp. 233-269] for treewidth-2 graphs. In addition, we obtain improved approximation ratios for $k$-outerplanar graphs on various problems for which approximation algorithms are based on probabilistic tree embeddings. We conjecture that these embeddings for $k$-outerplanar graphs may serve as building blocks for $\ell_1$ embeddings of more general metrics. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1137/S0895480102417379 | SODA |
Keywords | DocType | Volume |
constant distortion,polynomial time approximation scheme,outerplanar graph,approximation ratio,tree metrics,k-Outerplanar Graphs,general metrics,planar grid,approximation algorithm,general planar graph,probabilistic tree embeddings | Conference | 20 |
Issue | ISSN | Citations |
1 | 0895-4801 | 18 |
PageRank | References | Authors |
1.16 | 14 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chandra Chekuri | 1 | 3493 | 293.51 |
| Anupam Gupta | 2 | 2989 | 210.44 |
| Ilan Newman | 3 | 1149 | 82.18 |
| Yuri Rabinovich | 4 | 18 | 1.16 |
| Alistair Sinclair | 5 | 1506 | 308.40 |