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 $\beta$, with $\frac{1}{2} \leq\beta < 1$, where $G=(V,E)$ is a complete graph with a cost function $c$ satisfying the sharpened triangle inequality $$c(\{u,v\}) \le \beta \cdot \left( c(\{u,w\}) + c(\{w,v\}) \right)$$ for all $u,v,w \in V$. First, we give a linear-time approximation algorithm for these optimization problems with approximation ratio $\frac{\beta}{1-\beta}$ for any $\frac{1}{2} \le \beta < 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(2\beta-1)}{9(1-\beta)}\right)$-approximation algorithm for the 3-edge-connectivity subgraph problem for graphs satisfying the sharpened triangle inequality for $\frac{1}{2} \le \beta \le \frac{2}{3}$.
On $k$-Edge-Connectivity Problems with Sharpened Triangle Inequality
Proietti G;
2003
Abstract
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 $\beta$, with $\frac{1}{2} \leq\beta < 1$, where $G=(V,E)$ is a complete graph with a cost function $c$ satisfying the sharpened triangle inequality $$c(\{u,v\}) \le \beta \cdot \left( c(\{u,w\}) + c(\{w,v\}) \right)$$ for all $u,v,w \in V$. First, we give a linear-time approximation algorithm for these optimization problems with approximation ratio $\frac{\beta}{1-\beta}$ for any $\frac{1}{2} \le \beta < 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(2\beta-1)}{9(1-\beta)}\right)$-approximation algorithm for the 3-edge-connectivity subgraph problem for graphs satisfying the sharpened triangle inequality for $\frac{1}{2} \le \beta \le \frac{2}{3}$.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
