Network design via iterative rounding of setpair relaxations
type: Item
instance of: scholarly article
title: Network design via iterative rounding of setpair relaxations
zbMATH Open document ID: 1109.68136
author: Joseph Cheriyan
author: Santosh S. Vempala
author: Adrian Vetta
published in: Combinatorica
publication date: 2007-01-08T00:00:00Z
review text: An important class of network design problems asks for finding a minimum cost sub-network \(H\) of a given network \(G\) that satisfies some connectivity requirements. Perhaps the most famous work in this area is the seminal paper of \textit{M. X. Goemans} and \textit{D. P. Williamson} [SIAM J. Comput. 24, 296--317 (1995; Zbl 0834.68055)] which proposes a method for finding sub-networks satisfying a fairly general class of edge-connectivity requirements. The present paper continues a long succession of papers spawned by Goemans and Williamson's work, and it focuses on finding sub-networks satisfying given vertex-connectivity requirements. The vertex-connectivity requirements are expressed as an integer program whose constraints consist of a set of edge requirements over a family of setpairs. A setpair is simply a pair \((X,Y)\) of non-empty disjoint vertex sets. The edge connectivity requirements for a given setpair \((X,Y)\) is given by a requirement function \(f(X,Y)\) stating that the chosen subgraph must have at least \(f(X,Y)\) edges with one endpoint in \(X\) and the other endpoint in \(Y\). One of the problems considered in the paper is the \(k\)-vertex connectivity problem. Given a graph \(G=(V,E)\) with non-negative edge costs, the goal is to find a minimum cost, connected spanning subgraph \(H\), that remains connected even if \(k-1\) vertices are removed from it. This problem can be formulated as an integer program with the requirement function \(f(X,Y) =\max \{0,k-| V\setminus(X \cup Y)| \}\) defined over all setpairs \((X,Y)\) where \(X,Y \neq\emptyset\). The paper presents an approximation algorithm for solving the above kind of integer programs for the particular case when the requirement function \(f(X,Y)\) is skew bisupermodular. (Skew bisupermodular functions are a generalization of weakly supermodular and crossing bisupermodular functions.) This algorithm yields an \(O(\sqrt{n/(1-k/n)})\)-approximation algorithm for the \(k\)-vertex connectivity p…
reviewed by: Roberto Solis-Oba
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 5082299
zbMATH Keywords: approximation algorithm
zbMATH Keywords: network design
zbMATH Keywords: setpairs
zbMATH Keywords: skew bisupermodular functions
MaRDI profile type: Publication
full work available at URL: s00493-006-0016-z
OpenAlex ID: W1976459503
DOI: 10.1007/S00493-006-0016-Z
description: scientific article; zbMATH DE number 5082299