Improved Approximation Algorithms for Degree-bounded Network Design Problems with Node Connectivity Requirements

Speaker: Ali Vakilian , MIT

Date: Thursday, May 29, 2014

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G575

Event Type:

Room Description:

Host: Ilya Razenshteyn

Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: theory-seminars@csail.mit.edu, seminars@csail.mit.edu

Reminder Subject: TALK: Improved Approximation Algorithms for Degree-bounded Network Design Problems with Node Connectivity Requirements

Abstract:
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

Research Areas:

Impact Areas:

See other events that are part of the Algorithms and Complexity Series Fall 2013 / Spring 2014.

Created by Rebecca Yadegar at Tuesday, May 27, 2014 at 10:33 AM.