This paper's focus is the following family of problems, denoted k-ECSS, where
k denotes a positive integer: given a graph (V, E) and costs for each edge,
find a minimum-cost subset F of E such that (V, F) is k-edge-connected. For k=1
it is the spanning tree problem which is in P; for every other k it is APX-hard
and has a 2-approximation. Moreover, assuming P != NP, it is known that for
unit costs, the best possible approximation ratio is 1 + Theta(1/k) for k>1.
Our first main result is to determine the analogous asymptotic ratio for
general costs: we show there is a constant eps>0 so that for all k>1, finding a
(1+eps)-approximation for k-ECSS is NP-hard. Thus we establish a gap between
the unit-cost and general-cost versions, for large enough k. Next, we consider
the multi-subgraph cousin of k-ECSS, in which we are allowed to buy arbitrarily
many copies of any edges (i.e., F is now a multi-subset of E, with parallel
copies having the same cost as the original edge). Not so much is known about
this natural variant, but we conjecture that a (1 + Theta(1/k))-approximation
algorithm exists, and we describe an approach based on its naive linear
programming relaxation (LP) and graph decompositions. The LP is well-known ---
it is essentially the same as the Held-Karp TSP and the undirected LP for
Steiner tree --- and in order to further our understanding, we give a family of
extreme points for this LP with exponentially bad fractionality.