The Library
Improved approximation algorithms for degree-bounded network design problems with node connectivity requirements
Tools
Ene, Alina and Vakilian, Ali (2014) Improved approximation algorithms for degree-bounded network design problems with node connectivity requirements. In: 46th Annual ACM Symposium on Theory of Computing, New York, USA, 31 May - 3 Jun 2014. Published in: Proceedings of the 46th Annual ACM Symposium on Theory of Computing pp. 754-763. ISBN 9781450327107. doi:10.1145/2591796.2591837
|
PDF
WRAP_Ene_deg-bd-stoc.pdf - Requires a PDF viewer. Download (544Kb) | Preview |
Official URL: http://doi.acm.org/10.1145/2591796.2591837
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 satisfies 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 first (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.
Item Type: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Library of Congress Subject Headings (LCSH): | Graph theory | ||||
Journal or Publication Title: | Proceedings of the 46th Annual ACM Symposium on Theory of Computing | ||||
Publisher: | ACM | ||||
ISBN: | 9781450327107 | ||||
Official Date: | 2014 | ||||
Dates: |
|
||||
Page Range: | pp. 754-763 | ||||
DOI: | 10.1145/2591796.2591837 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Funder: | National Science Foundation (U.S.) (NSF), Chirag Foundation, Siebel Scholars Foundation | ||||
Grant number: | CCF-1016684 (NSF) | ||||
Embodied As: | 1 | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | 46th Annual ACM Symposium on Theory of Computing | ||||
Type of Event: | Other | ||||
Location of Event: | New York, USA | ||||
Date(s) of Event: | 31 May - 3 Jun 2014 | ||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year