Improved Approximation Algorithms for Degree-bounded Network Design Problems with Node Connectivity Requirements
Date: Thursday, May 29, 2014
Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone
Host: Ilya Razenshteyn
Contact: Rebecca Yadegar, firstname.lastname@example.org
Speaker URL: None
TALK: Improved Approximation Algorithms for Degree-bounded Network Design Problems with Node Connectivity Requirements
We consider degree bounded network design problems with element and vertex connectivity requirements. In the degree bounded Survivable Network Design (SNDP) problem, the input
is an undirected graph G = (V;E) with weights w(e) on the edges and degree bounds b(v) on the vertices, and connectivity requirements r(uv) for each pair uv of vertices.
The goal is to select a minimum-weight subgraph H of G that meets the connectivity requirements and it satises the degree bounds on the vertices: for each pair uv of vertices, H has r(uv) disjoint paths between u and v; additionally, each
vertex v is incident to at most b(v) edges in H. We give the rst (O(1);O(1) b(v)) bicriteria approximation algorithms for the degree-bounded SNDP problem with element connectivity requirements and for several degree-bounded SNDP
problems with vertex connectivity requirements. Our algorithms construct a subgraph H whose weight is at most O(1)times the optimal such that each vertex v is incident to at most O(1) b(v) edges in H. We can also extend our approach
to network design problems in directed graphs with
out-degree constraints to obtain (O(1);O(1) b+(v)) bicriteria approximation
Joint work with Alina Ene
Created by Rebecca Yadegar at Tuesday, May 27, 2014 at 10:33 AM.