On generalizations of network design problems with degree bounds

N. Bansal, R. Khandekar, J. Könemann, V. Nagarajan, B. Peis

Research output: Contribution to journalArticleAcademicpeer-review

14 Citations (Scopus)

Abstract

Iterative rounding and relaxation have arguably become the method of choice in dealing with unconstrained and constrained network design problems. In this paper we extend the scope of the iterative relaxation method in two directions: (1) by handling more complex degree constraints in the minimum spanning tree problem (namely laminar crossing spanning tree), and (2) by incorporating ‘degree bounds’ in other combinatorial optimization problems such as matroid intersection and lattice polyhedra. We give new or improved approximation algorithms, hardness results, and integrality gaps for these problems. Our main result is a (1, b + O(log n))-approximation algorithm for the minimum crossing spanning tree (MCST) problem with laminar degree constraints. The laminar MCST problem is a natural generalization of the well-studied bounded-degree MST, and is a special case of general crossing spanning tree. We give an additive O(log c m) hardness of approximation for general MCST, even in the absence of costs (c > 0 is a fixed constant, and m is the number of degree constraints). This also leads to a multiplicative O(log c m) hardness of approximation for the robust k-median problem (Anthony et al. in Math Oper Res 35:79–101, 2010), improving over the previously known factor 2 hardness. We then consider the crossing contra-polymatroid intersection problem and obtain a (2, 2b + ¿ - 1)-approximation algorithm, where ¿ is the maximum element frequency. This models for example the degree-bounded spanning-set intersection in two matroids. Finally, we introduce the crossing latticep olyhedron problem, and obtain a (1, b + 2¿ - 1) approximation algorithm under certain condition. This result provides a unified framework and common generalization of various problems studied previously, such as degree bounded matroids.
Original languageEnglish
Pages (from-to)479-506
Number of pages28
JournalMathematical Programming
Volume141
Issue number1-2
DOIs
Publication statusPublished - 2013

Fingerprint

Approximation algorithms
Network Design
Hardness
Spanning tree
Approximation Algorithms
Hardness of Approximation
Combinatorial optimization
Minimum Spanning Tree
Matroid
Intersection
Matroid Intersection
Polymatroid
Generalization
Integrality
Relaxation Method
Rounding
Combinatorial Optimization Problem
Costs
Polyhedron
Multiplicative

Cite this

Bansal, N. ; Khandekar, R. ; Könemann, J. ; Nagarajan, V. ; Peis, B. / On generalizations of network design problems with degree bounds. In: Mathematical Programming. 2013 ; Vol. 141, No. 1-2. pp. 479-506.
@article{46f8850bf52642c2941d37fbcd504139,
title = "On generalizations of network design problems with degree bounds",
abstract = "Iterative rounding and relaxation have arguably become the method of choice in dealing with unconstrained and constrained network design problems. In this paper we extend the scope of the iterative relaxation method in two directions: (1) by handling more complex degree constraints in the minimum spanning tree problem (namely laminar crossing spanning tree), and (2) by incorporating ‘degree bounds’ in other combinatorial optimization problems such as matroid intersection and lattice polyhedra. We give new or improved approximation algorithms, hardness results, and integrality gaps for these problems. Our main result is a (1, b + O(log n))-approximation algorithm for the minimum crossing spanning tree (MCST) problem with laminar degree constraints. The laminar MCST problem is a natural generalization of the well-studied bounded-degree MST, and is a special case of general crossing spanning tree. We give an additive O(log c m) hardness of approximation for general MCST, even in the absence of costs (c > 0 is a fixed constant, and m is the number of degree constraints). This also leads to a multiplicative O(log c m) hardness of approximation for the robust k-median problem (Anthony et al. in Math Oper Res 35:79–101, 2010), improving over the previously known factor 2 hardness. We then consider the crossing contra-polymatroid intersection problem and obtain a (2, 2b + ¿ - 1)-approximation algorithm, where ¿ is the maximum element frequency. This models for example the degree-bounded spanning-set intersection in two matroids. Finally, we introduce the crossing latticep olyhedron problem, and obtain a (1, b + 2¿ - 1) approximation algorithm under certain condition. This result provides a unified framework and common generalization of various problems studied previously, such as degree bounded matroids.",
author = "N. Bansal and R. Khandekar and J. K{\"o}nemann and V. Nagarajan and B. Peis",
year = "2013",
doi = "10.1007/s10107-012-0537-8",
language = "English",
volume = "141",
pages = "479--506",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer",
number = "1-2",

}

Bansal, N, Khandekar, R, Könemann, J, Nagarajan, V & Peis, B 2013, 'On generalizations of network design problems with degree bounds', Mathematical Programming, vol. 141, no. 1-2, pp. 479-506. https://doi.org/10.1007/s10107-012-0537-8

On generalizations of network design problems with degree bounds. / Bansal, N.; Khandekar, R.; Könemann, J.; Nagarajan, V.; Peis, B.

In: Mathematical Programming, Vol. 141, No. 1-2, 2013, p. 479-506.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - On generalizations of network design problems with degree bounds

AU - Bansal, N.

AU - Khandekar, R.

AU - Könemann, J.

AU - Nagarajan, V.

AU - Peis, B.

PY - 2013

Y1 - 2013

N2 - Iterative rounding and relaxation have arguably become the method of choice in dealing with unconstrained and constrained network design problems. In this paper we extend the scope of the iterative relaxation method in two directions: (1) by handling more complex degree constraints in the minimum spanning tree problem (namely laminar crossing spanning tree), and (2) by incorporating ‘degree bounds’ in other combinatorial optimization problems such as matroid intersection and lattice polyhedra. We give new or improved approximation algorithms, hardness results, and integrality gaps for these problems. Our main result is a (1, b + O(log n))-approximation algorithm for the minimum crossing spanning tree (MCST) problem with laminar degree constraints. The laminar MCST problem is a natural generalization of the well-studied bounded-degree MST, and is a special case of general crossing spanning tree. We give an additive O(log c m) hardness of approximation for general MCST, even in the absence of costs (c > 0 is a fixed constant, and m is the number of degree constraints). This also leads to a multiplicative O(log c m) hardness of approximation for the robust k-median problem (Anthony et al. in Math Oper Res 35:79–101, 2010), improving over the previously known factor 2 hardness. We then consider the crossing contra-polymatroid intersection problem and obtain a (2, 2b + ¿ - 1)-approximation algorithm, where ¿ is the maximum element frequency. This models for example the degree-bounded spanning-set intersection in two matroids. Finally, we introduce the crossing latticep olyhedron problem, and obtain a (1, b + 2¿ - 1) approximation algorithm under certain condition. This result provides a unified framework and common generalization of various problems studied previously, such as degree bounded matroids.

AB - Iterative rounding and relaxation have arguably become the method of choice in dealing with unconstrained and constrained network design problems. In this paper we extend the scope of the iterative relaxation method in two directions: (1) by handling more complex degree constraints in the minimum spanning tree problem (namely laminar crossing spanning tree), and (2) by incorporating ‘degree bounds’ in other combinatorial optimization problems such as matroid intersection and lattice polyhedra. We give new or improved approximation algorithms, hardness results, and integrality gaps for these problems. Our main result is a (1, b + O(log n))-approximation algorithm for the minimum crossing spanning tree (MCST) problem with laminar degree constraints. The laminar MCST problem is a natural generalization of the well-studied bounded-degree MST, and is a special case of general crossing spanning tree. We give an additive O(log c m) hardness of approximation for general MCST, even in the absence of costs (c > 0 is a fixed constant, and m is the number of degree constraints). This also leads to a multiplicative O(log c m) hardness of approximation for the robust k-median problem (Anthony et al. in Math Oper Res 35:79–101, 2010), improving over the previously known factor 2 hardness. We then consider the crossing contra-polymatroid intersection problem and obtain a (2, 2b + ¿ - 1)-approximation algorithm, where ¿ is the maximum element frequency. This models for example the degree-bounded spanning-set intersection in two matroids. Finally, we introduce the crossing latticep olyhedron problem, and obtain a (1, b + 2¿ - 1) approximation algorithm under certain condition. This result provides a unified framework and common generalization of various problems studied previously, such as degree bounded matroids.

U2 - 10.1007/s10107-012-0537-8

DO - 10.1007/s10107-012-0537-8

M3 - Article

VL - 141

SP - 479

EP - 506

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 1-2

ER -