Network Design via Core Detouring for Problems Without a Core

Some of the currently best-known approximation algorithms for network design are based on random sampling. One of the key steps of such algorithms is connecting a set of source nodes to a random subset of them. In a recent work [Eisenbrand,Grandoni,Rothvo\ss,Schäfer-SODA'08], a new technique, \emph{core-detouring}, is described to bound the mentioned connection cost. This is achieved by defining a sub-optimal connection scheme, where paths are detoured through a proper connected subgraph (core). The cost of the detoured paths is bounded against the cost of the core and of the distances from the sources to the core. The analysis then boils down to proving the \emph{existence} of a convenient core. For some problems, such as connected facility location and single-sink rent-or-buy, the choice of the core is obvious (i.e., the Steiner tree in the optimum solution). Other, more complex network design problems do not exhibit any such core. In this paper we show that core-detouring can be nonetheless successfully applied. The basic idea is constructing a convenient core by manipulating the optimal solution in a proper (not necessarily trivial) way. We illustrate that by presenting improved approximation algorithms for two well-studied problems: virtual private network design and single-sink buy-at-bulk.

Abramsky, Samson
Gavoille, Cyril
Kirchner, Claude
Meyer auf der Heide, Friedhelm
Spirakis, Paul
Published in:
Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I, 490-502
Presented at:
37th International Colloquium on Automata, Languages and Programming (ICALP'10), Bordeaux, France, July 5-10, 2010

Note: The status of this file is: Anyone

 Record created 2010-07-13, last modified 2020-10-28

Download fulltextPDF
External link:
Download fulltextURL
Rate this document:

Rate this document:
(Not yet reviewed)