Approximating the smallest k-edge connected spanning subgraph by LP-rounding

Approximating the smallest k-edge connected spanning subgraph by LP-rounding

0.00 Avg rating0 Votes
Article ID: iaor200969372
Country: United States
Volume: 53
Issue: 4
Start Page Number: 345
End Page Number: 357
Publication Date: Jul 2009
Journal: Networks
Authors: , , ,
Keywords: graphs, programming: linear
Abstract:

The smallest k-ECSS problem is, given a graph along with an integer k, find a spanning subgraph that is k-edge connected and contains the fewest possible number of edges. We examine a natural approximation algorithm based on rounding an LP solution. A tight bound on the approximation ratio is 1 + 3/k for undirected graphs with k > 1 odd, 1 + 2/k for undirected graphs with k even, and 1 + 2/k for directed graphs with k arbitrary. Using iterated rounding improves the first upper bound to 1 + 2/k. On the hardness side we show that for some absolute constant c > 0, for any integer k ≥ 2, a polynomial-time algorithm approximating the smallest k-ECSS on undirected (directed) multigraphs to within ratio 1 + c/k would imply P = NP.

Reviews

Required fields are marked *. Your email address will not be published.