20131001
On generalizations of network design problems with degree bounds
Publication
Publication
Mathematical Programming , Volume 141  Issue 12 p. 479 506
Iterative rounding and relaxation have arguably become the method of choice in dealing with unconstrained and constrained network design problems. In this paper we extend the scope of the iterative relaxation method in two directions: (1) by handling more complex degree constraints in the minimum spanning tree problem (namely laminar crossing spanning tree), and (2) by incorporating ‘degree bounds’ in other combinatorial optimization problems such as matroid intersection and lattice polyhedra. We give new or improved approximation algorithms, hardness results, and integrality gaps for these problems. Our main result is a (1, b + O(log n))approximation algorithm for the minimum crossing spanning tree (MCST) problem with laminar degree constraints. The laminar MCST problem is a natural generalization of the wellstudied boundeddegree MST, and is a special case of general crossing spanning tree. We give an additive Ω(log c m) hardness of approximation for general MCST, even in the absence of costs (c > 0 is a fixed constant, and m is the number of degree constraints). This also leads to a multiplicative Ω(log c m) hardness of approximation for the robust kmedian problem (Anthony et al. in Math Oper Res 35:79–101, 2010), improving over the previously known factor 2 hardness. We then consider the crossing contrapolymatroid intersection problem and obtain a (2, 2b + Δ − 1)approximation algorithm, where Δ is the maximum element frequency. This models for example the degreebounded spanningset intersection in two matroids. Finally, we introduce the crossing latticep olyhedron problem, and obtain a (1, b + 2Δ − 1) approximation algorithm under certain condition. This result provides a unified framework and common generalization of various problems studied previously, such as degree bounded matroids.
Additional Metadata  

Springer  
Mathematical Programming  
Organisation  Computer Security 
Bansal, N, Khandekar, R, Könemann, J, Nagarajan, V, & Peis, B. (2013). On generalizations of network design problems with degree bounds. Mathematical Programming, 141(12), 479–506.
