Bansal, NikhilKhandekar, RohitKönemann, JochenNagarajan, ViswanathPeis, Britta2022-05-112022-05-1120092197-8085https://depositonce.tu-berlin.de/handle/11303/16909http://dx.doi.org/10.14279/depositonce-15687The 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.en510 Mathematikiterative roundinglattice polyedrasubmodular functionsdegree bounded spanning treesResearch Paper