Approximating a 2-edge-connected subgraph problem Higher-Confidence Integer Programming

We consider the following network design problem. We are given a graph. We wish to select a minimum-cost subset of edges such that removing any edge leaves all pairs connected. This is a 2-edge-connected network design problem. Each edge has two costs, one for building a single connection and one for building two parallel independent connections. There is a buy-at-bulk discount for the parallel edges. That is, it costs less than twice the cost of the single channel. Our problem is a special-case of the buy-at-bulk network design with protection problem. Both the general problem and our variant are NP-complete, and thus it is reasonable to find provably-good approximation algorithms. An α approximation for an optimization problem is a provably efficient algorithm that guarantees a solution no more than α times optimal. Antonakopoulos et. al. [1] give the best currently known approximation algorithm for the general buy-at-bulk with protection problem, which is actively used for designing optical communication networks. This general problem specifies a set of pairs of nodes to connect rather than requiring connection of all pairs. There is a bandwidth requirement for each pair. The network must be able to robustly and simultaneously serve all these pairs (e.g connectivity from New York to L