TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)2009

COGA 5-Wheel

Page Content

to Navigation

Preprints 2009

On Generalizations of Network Design Problems with Degree Bounds
Citation key Report-007-2009
Author Nikhil Bansal and Rohit Khandekar and Jochen Könemann and Viswanath Nagarajan and Britta Peis
Year 2009
Number 007
Month feb
Institution Technische Universität Berlin, Institut für Mathematik
Abstract 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.<br> - 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.<br> - 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).<br> - 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.
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe