- Improved Approximation Algo...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in May 2014

## 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

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

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