On Generalizations of Network Design Problems with Degree Bounds
| dc.contributor.author | Bansal, Nikhil | |
| dc.contributor.author | Khandekar, Rohit | |
| dc.contributor.author | Könemann, Jochen | |
| dc.contributor.author | Nagarajan, Viswanath | |
| dc.contributor.author | Peis, Britta | |
| dc.date.accessioned | 2022-05-11T12:11:48Z | |
| dc.date.available | 2022-05-11T12:11:48Z | |
| dc.date.issued | 2009 | |
| dc.description.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. | en |
| dc.identifier.issn | 2197-8085 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/16909 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-15687 | |
| dc.language.iso | en | |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | |
| dc.subject.ddc | 510 Mathematik | en |
| dc.subject.other | iterative rounding | en |
| dc.subject.other | lattice polyedra | en |
| dc.subject.other | submodular functions | en |
| dc.subject.other | degree bounded spanning trees | en |
| dc.title | On Generalizations of Network Design Problems with Degree Bounds | en |
| dc.type | Research Paper | en |
| dc.type.version | submittedVersion | en |
| tub.accessrights.dnb | free | |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |
| tub.series.issuenumber | 2009, 07 | en |
| tub.series.name | Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin | en |
Files
Original bundle
1 - 1 of 1