Loading…
On Generalizations of Network Design Problems with Degree Bounds
Bansal, Nikhil; Khandekar, Rohit; Könemann, Jochen; Nagarajan, Viswanath; Peis, Britta
Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
The problem of designing efficient networks with degree-bound constraints has received a lot of attention recently. In this paper, we study several generalizations of this fundamental problem. Our generalizations are of the following two types:
- Generalize constraints on vertex-degree to arbitrary subsets of edges.
- Generalize the underlying network design problem to other combinatorial optimization problems like polymatroid intersection and lattice polyhedra.
We present several algorithmic results and lower bounds for these problems. At a high level, our algorithms are based on the iterative rounding/relaxation technique introduced in the context of degree bounded network design by Lau et al. and Singh-Lau. However many new ideas are required to apply this technique to the problems we consider. Our main results are:
-We consider the minimum crossing spanning tree problem in the case that the ""degree constraints"" have a laminar structure (this generalizes the well-known bounded degree MST). We provide a (1,b+O(log n)) bicriteria approximation for this problem, that improves over earlier results.
- We introduce the minimum crossing polymatroid intersection problem, and give a (2,2b+Delta-1) bicriteria approximation (where Delta is the maximum number of degree-constraints that an element is part of). In the special case of bounded-degree arborescence (here Delta=1), this improves the previously best known (2,2b+2) bound to (2,2b).
- We also introduce the minimum crossing lattice polyhedra problem, and obtain a (1,b+2*Delta-1) bicriteria approximation under certain condition. This result provides a unified framework and common generalization of various problems studied previously, such as degree bounded matroids.
