Iterative rounding approximation algorithms for degree-bounded node-connectivity network design
| Speaker: | Takuro Fukunaga |
|---|---|
| Affiliation: | Kyoto University |
| Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
We consider the problem of finding a minimum edge cost subgraph of an undirected or a directed graph satisfying given connectivity requirements and degree bounds b on nodes. We present an iterative rounding algorithm of the set-pair LP relaxation for this problem. When the graph is undirected and the connectivity requirements are on the element-connectivity with maximum value k, our algorithm computes a solution that is an O(k)-approximation for the edge cost in which the degree of each node v is at most O(k)b(v). We also consider the no edge cost case where the objective is to find a subgraph satisfying connectivity requirements and degree bounds. Our algorithm for this case outputs a solution in which the degree of each node v is at most 6b(v) + O(k^2). These algorithms can be extended to other well-studied undirected node-connectivity requirements such as spanning-, subset- and root-connectivity. When the graph is directed and the connectivity requirement is spanning k-out-connectivity from a root, our algorithm computes a solution that is a 2-approximation for the edge cost in which the degree of each node v is at most 2b(v) + O(k).
This is a joint work with R. Ravi (CMU).