  In the k-edge-connected spanning subgraph problem we are given a graph (V, E)
and costs for each edge, and want to find a minimum-cost subset F of E such
that (V, F) is k-edge-connected. 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,
establishing a gap between the unit-cost and general-cost versions. Next, we
consider the multi-subgraph cousin of k-ECSS, in which we purchase a
multi-subset F of E, with unlimited parallel copies available at the same cost
as the original edge. We conjecture that a (1 + Theta(1/k))-approximation
algorithm exists, and we describe an approach based on graph decompositions
applied to its natural linear programming (LP) relaxation. The LP is
essentially equivalent to the Held-Karp LP for TSP and the undirected LP for
Steiner tree. We give a family of extreme points for the LP which are more
complex than those previously known.
