direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 07-2009

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Title
On Generalizations of Network Design Problems with Degree Bounds
Authors
Nikhil Bansal, Rohit Khandekar, Jochen Könemann, Viswanath Nagarajan, and Britta Peis
Classification
not available
Keywords
iterative rounding,lattice polyedra, submodular functions, degree bounded spanning trees
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.

- 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.
Source
Download as [PDF]
Title: Source

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe