The edge-connectivity problem is to find a minimum-cost
k-edge-connected spanning subgraph of an edge-weighted, undirected graph
G for any given
G and
k. Here we consider its APX-hard subproblems with respect to the parameter
β, with
$
\frac{1}
{2}
$
\frac{1}
{2}
⩽
β < 1, where
G = (
V, E) is a complete graph with a cost function
c satisfying the sharpened triangle inequality
|
$
c\left( {\left\{ {u,v} \right\}} \right) \leqslant \beta .\left( {c\left\{ {u,w} \right\}} \right) + c\left( {\left\{ {w,v} \right\}} \right)
$
c\left( {\left\{ {u,v} \right\}} \right) \leqslant \beta .\left( {c\left\{ {u,w} \right\}} \right) + c\left( {\left\{ {w,v} \right\}} \right)
|
for all
u, v, w ∈
V.
First, we give a linear-time approximation algorithm for these optimization problems with approximation ratio
$
\frac{\beta }
{{1 - \beta }}
$
\frac{\beta }
{{1 - \beta }}
for any
$
\frac{1}
{2}
$
\frac{1}
{2}
⩽
β < 1, which does not depend on
k.
The result above is based on a rough combinatorial argumentation. We sophisticate our combinatorial consideration in order
to design a
$
\left( {1 + \frac{{5\left( {2\beta - 1} \right)}}
{{9\left( {1 - \beta } \right)}}} \right)
$
\left( {1 + \frac{{5\left( {2\beta - 1} \right)}}
{{9\left( {1 - \beta } \right)}}} \right)
approximation algorithm for the 3-edge-connectivity subgraph problem for graphs satisfying the sharpened triangle inequality
for
$
\frac{1}
{2}
$
\frac{1}
{2}
⩽
β ⩽
$
\frac{2}
{3}
$
\frac{2}
{3}
.
This work was partially supported by DFG-grant Hr 14/5-1, the CNR-Agenzia 2000 Program, under Grants No. CNRC00CAB8 and CNRG003EF8,
and the Research Project REAL-WINE, partially funded by the Italian Ministry of Education, University and Research.