Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
On the Complexity of the Asymmetric VPN Problem
verfasst von : Thomas Rothvoß, Laura Sanità
Erschienen in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We give the first constant factor approximation algorithm for the asymmetric Virtual Private Network (
Vpn
) problem with arbitrary concave costs. We even show the stronger result, that there is always a tree solution of cost at most 2·
OPT
and that a tree solution of (expected) cost at most 49.84·
OPT
can be determined in polynomial time.
For the case of linear cost we obtain a
$(2+\varepsilon\frac{\mathcal R}{\mathcal S})$
-approximation algorithm for any fixed
ε
> 0, where
$\mathcal{S}$
and
$\mathcal{R}$
(
$\mathcal{R} \geq \mathcal{S}$
) denote the outgoing and ingoing demand, respectively.
Furthermore, we answer an outstanding open question about the complexity status of the so called
balanced
$\textsc{Vpn}$
problem by proving its
NP
-hardness.