Network design with edge-connectivity and degree constraints

Abstract

We consider the following network design problem; Given a vertex set V with a metric cost c on V, an integer k≥1, and a degree specification b, find a minimum cost k-edge-connected multigraph on V under the constraint that the degree of each vertex v∈V is equal to b(v). This problem generalizes metric TSP. In this paper, we show that the problem admits a ρ-approximation algorithm if b(v)≥2, v∈V, where ρ=2.5 if k is even, and ρ=2.5+1.5/k if k is odd. We also prove that the digraph version of this problem admits a 2.5-approximation algorithm and discuss some generalization of metric TSP.