- 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.}, Url = {http://www.redaktion.tu-berlin.de/fileadmin/i26/download/AG_DiskAlg/FG_KombOptGraphAlg/preprints/2009/Report-007-2009.pdf}, Keywords = {iterative rounding,lattice polyedra, submodular functions, degree bounded spanning trees} }