On k-connectivity problems with sharpened triangle inequality

AbstractThe k-connectivity problem is to find a minimum-cost k-edge- or k-vertex-connected spanning subgraph of an edge-weighted, undirected graph G for any given G and k. Here, we consider its NP-hard subproblems with respect to the parameter β, with 12<β<1, where G=(V,E) is a complete graph with a cost function c satisfying the sharpened triangle inequality c({u,v})⩽β⋅(c({u,w})+c({w,v})) for all u,v,w∈V.First, we give a simple linear-time approximation algorithm for these optimization problems with approximation ratio β1−β for any 12⩽β<1, which improves the known approximation ratios for 12<β