On some network design problems with degree constraints

Rohit Khandekar, Guy Kortsarz, Zeev Nutov

Research output: Contribution to journalArticle

15 Citations (Scopus)

Abstract

We study several network design problems with degree constraints. For the minimum-cost Degree-Constrained 2-Node-Connected Subgraph problem, we obtain the first non-trivial bicriteria approximation algorithm, with 5b(v)+3 violation for the degrees and a 4-approximation for the cost. This improves upon the logarithmic degree violation and no cost guarantee obtained by Feder, Motwani, and Zhu (2006). Then we consider the problem of finding an arborescence with at least k terminals and with minimum maximum outdegree. We show that the natural LP-relaxation has a gap of Ω(k) or Ω(n1/4) with respect to the multiplicative degree bound violation. We overcome this hurdle by a combinatorial O((klogk)/Δ*)-approximation algorithm, where Δ* denotes the maximum degree in the optimum solution. We also give an Ω(logn) lower bound on approximating this problem. Then we consider the undirected version of this problem, however, with an extra diameter constraint, and give an Ω(logn) lower bound on the approximability of this version. We also consider a closely related Prize-Collecting Degree-Constrained Edge-Connectivity Survivable Network problem, and obtain several results in this direction by reducing the prize-collecting variant to the regular one. Finally, we consider the Terminal Steiner Tree problem, which is a simple variant of the Degree-Constrained Steiner Tree problem, when some terminals are required to be leaves. We show that this seemingly simple problem is equivalent to the Group Steiner Tree problem.

Original languageEnglish (US)
Pages (from-to)725-736
Number of pages12
JournalJournal of Computer and System Sciences
Volume79
Issue number5
DOIs
StatePublished - Aug 1 2013

Fingerprint

Network Design
Approximation algorithms
Steiner Tree Problem
Costs
Approximation Algorithms
Lower bound
LP Relaxation
Edge-connectivity
Bicriteria
Approximability
Maximum Degree
Subgraph
Multiplicative
Logarithmic
Denote
Approximation
Vertex of a graph

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Applied Mathematics
  • Computer Networks and Communications
  • Computational Theory and Mathematics

Keywords

  • Approximation algorithms
  • Degree-constraints
  • Network design

Cite this

Khandekar, Rohit ; Kortsarz, Guy ; Nutov, Zeev. / On some network design problems with degree constraints. In: Journal of Computer and System Sciences. 2013 ; Vol. 79, No. 5. pp. 725-736.
@article{1c61316e23be4e79b20c955500bda910,
title = "On some network design problems with degree constraints",
abstract = "We study several network design problems with degree constraints. For the minimum-cost Degree-Constrained 2-Node-Connected Subgraph problem, we obtain the first non-trivial bicriteria approximation algorithm, with 5b(v)+3 violation for the degrees and a 4-approximation for the cost. This improves upon the logarithmic degree violation and no cost guarantee obtained by Feder, Motwani, and Zhu (2006). Then we consider the problem of finding an arborescence with at least k terminals and with minimum maximum outdegree. We show that the natural LP-relaxation has a gap of Ω(k) or Ω(n1/4) with respect to the multiplicative degree bound violation. We overcome this hurdle by a combinatorial O((klogk)/Δ*)-approximation algorithm, where Δ* denotes the maximum degree in the optimum solution. We also give an Ω(logn) lower bound on approximating this problem. Then we consider the undirected version of this problem, however, with an extra diameter constraint, and give an Ω(logn) lower bound on the approximability of this version. We also consider a closely related Prize-Collecting Degree-Constrained Edge-Connectivity Survivable Network problem, and obtain several results in this direction by reducing the prize-collecting variant to the regular one. Finally, we consider the Terminal Steiner Tree problem, which is a simple variant of the Degree-Constrained Steiner Tree problem, when some terminals are required to be leaves. We show that this seemingly simple problem is equivalent to the Group Steiner Tree problem.",
keywords = "Approximation algorithms, Degree-constraints, Network design",
author = "Rohit Khandekar and Guy Kortsarz and Zeev Nutov",
year = "2013",
month = "8",
day = "1",
doi = "https://doi.org/10.1016/j.jcss.2013.01.019",
language = "English (US)",
volume = "79",
pages = "725--736",
journal = "Journal of Computer and System Sciences",
issn = "0022-0000",
publisher = "Academic Press Inc.",
number = "5",

}

On some network design problems with degree constraints. / Khandekar, Rohit; Kortsarz, Guy; Nutov, Zeev.

In: Journal of Computer and System Sciences, Vol. 79, No. 5, 01.08.2013, p. 725-736.

Research output: Contribution to journalArticle

TY - JOUR

T1 - On some network design problems with degree constraints

AU - Khandekar, Rohit

AU - Kortsarz, Guy

AU - Nutov, Zeev

PY - 2013/8/1

Y1 - 2013/8/1

N2 - We study several network design problems with degree constraints. For the minimum-cost Degree-Constrained 2-Node-Connected Subgraph problem, we obtain the first non-trivial bicriteria approximation algorithm, with 5b(v)+3 violation for the degrees and a 4-approximation for the cost. This improves upon the logarithmic degree violation and no cost guarantee obtained by Feder, Motwani, and Zhu (2006). Then we consider the problem of finding an arborescence with at least k terminals and with minimum maximum outdegree. We show that the natural LP-relaxation has a gap of Ω(k) or Ω(n1/4) with respect to the multiplicative degree bound violation. We overcome this hurdle by a combinatorial O((klogk)/Δ*)-approximation algorithm, where Δ* denotes the maximum degree in the optimum solution. We also give an Ω(logn) lower bound on approximating this problem. Then we consider the undirected version of this problem, however, with an extra diameter constraint, and give an Ω(logn) lower bound on the approximability of this version. We also consider a closely related Prize-Collecting Degree-Constrained Edge-Connectivity Survivable Network problem, and obtain several results in this direction by reducing the prize-collecting variant to the regular one. Finally, we consider the Terminal Steiner Tree problem, which is a simple variant of the Degree-Constrained Steiner Tree problem, when some terminals are required to be leaves. We show that this seemingly simple problem is equivalent to the Group Steiner Tree problem.

AB - We study several network design problems with degree constraints. For the minimum-cost Degree-Constrained 2-Node-Connected Subgraph problem, we obtain the first non-trivial bicriteria approximation algorithm, with 5b(v)+3 violation for the degrees and a 4-approximation for the cost. This improves upon the logarithmic degree violation and no cost guarantee obtained by Feder, Motwani, and Zhu (2006). Then we consider the problem of finding an arborescence with at least k terminals and with minimum maximum outdegree. We show that the natural LP-relaxation has a gap of Ω(k) or Ω(n1/4) with respect to the multiplicative degree bound violation. We overcome this hurdle by a combinatorial O((klogk)/Δ*)-approximation algorithm, where Δ* denotes the maximum degree in the optimum solution. We also give an Ω(logn) lower bound on approximating this problem. Then we consider the undirected version of this problem, however, with an extra diameter constraint, and give an Ω(logn) lower bound on the approximability of this version. We also consider a closely related Prize-Collecting Degree-Constrained Edge-Connectivity Survivable Network problem, and obtain several results in this direction by reducing the prize-collecting variant to the regular one. Finally, we consider the Terminal Steiner Tree problem, which is a simple variant of the Degree-Constrained Steiner Tree problem, when some terminals are required to be leaves. We show that this seemingly simple problem is equivalent to the Group Steiner Tree problem.

KW - Approximation algorithms

KW - Degree-constraints

KW - Network design

UR - http://www.scopus.com/inward/record.url?scp=84875220841&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84875220841&partnerID=8YFLogxK

U2 - https://doi.org/10.1016/j.jcss.2013.01.019

DO - https://doi.org/10.1016/j.jcss.2013.01.019

M3 - Article

VL - 79

SP - 725

EP - 736

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

SN - 0022-0000

IS - 5

ER -