NDLI: Survivable Network Design with Degree or Order Constraints

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Singh, Mohit Salavatipour, Mohammad R. Naor, Joseph (Seffi) Lau, Lap Chi
Copyright Year	2009
Abstract	We present algorithmic and hardness results for network design problems with degree or order constraints. The first problem we consider is the Survivable Network Design problem with degree constraints on vertices. The objective is to find a minimum cost subgraph which satisfies connectivity requirements between vertices and also degree upper bounds $B_v$ on the vertices. This includes the well-studied Minimum Bounded Degree Spanning Tree problem as a special case. Our main result is a $(2,2B_v+3)$-approximation algorithm for the edge-connectivity Survivable Network Design problem with degree constraints, where the cost of the returned solution is at most twice the cost of an optimum solution (satisfying the degree bounds) and the degree of each vertex v is at most $2B_v+3$. This implies the first constant factor (bicriteria) approximation algorithms for many degree constrained network design problems, including the Minimum Bounded Degree Steiner Forest problem. Our results also extend to directed graphs and provide the first constant factor (bicriteria) approximation algorithms for the Minimum Bounded Degree Arborescence problem and the Minimum Bounded Degree Strongly k-Edge-Connected Subgraph problem. In contrast, we show that the vertex-connectivity Survivable Network Design problem with degree constraints is hard to approximate, even when the cost of every edge is zero. A striking aspect of our algorithmic result is its simplicity. It is based on the iterative relaxation method, which is an extension of Jain's iterative rounding method. This provides an elegant and unifying algorithmic framework for a broad range of network design problems. We also study the problem of finding a minimum cost $\lambda$-edge-connected subgraph with at least k vertices, which we call the $(k,\lambda)$-subgraph problem. This generalizes some well-studied classical problems such as the k-MST and the minimum cost $\lambda$-edge-connected subgraph problems. We give a polylogarithmic approximation for the $(k,2)$-subgraph problem. However, by relating it to the Densest k-Subgraph problem, we provide evidence that the $(k,\lambda)$-subgraph problem might be hard to approximate for arbitrary $\lambda$.
Starting Page	1062
Ending Page	1087
Page Count	26
File Format	PDF
ISSN	00975397
DOI	10.1137/070700620
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	3 (Special Section On The Thirty-Ninth Annual ACM Symposium On Theory Of Computing (STOC 2007))
Volume Number	39
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2009-09-02
Access Restriction	Subscribed
Subject Keyword	$\lambda$-edge-connected survivable network design k-subgraph Approximation algorithms approximation algorithms Graph algorithms degree bounded Analysis of algorithms
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Survivable network design with degree or order constraints

Additive Approximation for Bounded Degree Survivable Network Design

Survivable network design with degree or order constraints (2009)

Iterated Rounding Algorithms for the Smallest k-Edge Connected Spanning Subgraph

An $O(\log^2{k})$-Approximation Algorithm for the $k$-Vertex Connected Spanning Subgraph Problem

An Improved Analysis for Approximating the Smallest k-Edge Connected Spanning Subgraph of a Multigraph

Degree Bounded Network Design with Metric Costs

Survivable network design with degree or order constraints (Extended Abstract) (2007)

Additive approximation for bounded degree survivable network design

Survivable Network Design with Degree or Order Constraints

Similar Documents

Survivable network design with degree or order constraints

Additive Approximation for Bounded Degree Survivable Network Design

Survivable network design with degree or order constraints (2009)

Iterated Rounding Algorithms for the Smallest k-Edge Connected Spanning Subgraph

An $O(\log^2{k})$-Approximation Algorithm for the $k$-Vertex Connected Spanning Subgraph Problem

An Improved Analysis for Approximating the Smallest k-Edge Connected Spanning Subgraph of a Multigraph

Degree Bounded Network Design with Metric Costs

Survivable network design with degree or order constraints (Extended Abstract) (2007)

Additive approximation for bounded degree survivable network design

Survivable Network Design with Degree or Order Constraints