On generalizations of network design problems with degree bounds

• 成果类型: Article
• 署名作者: Bansal, Nikhil; Khandekar, Rohit; Koenemann, Jochen; Nagarajan, Viswanath; Peis, Britta
• 署名单位: Eindhoven University of Technology; International Business Machines (IBM); IBM USA; University of Waterloo; Technical University of Berlin
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-012-0537-8
• 发表日期: 2013
• 页码: 479-506
• 关键词: APPROXIMATION ALGORITHM; location-problems; spanning-trees; LOCAL SEARCH; msts; lattices

摘要

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 well-studied bounded-degree MST, and is a special case of general crossing spanning tree. We give an additive Omega(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 Omega(log (c) m) hardness of approximation for the robust k-median 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 contra-polymatroid intersection problem and obtain a (2, 2b + Delta - 1)-approximation algorithm, where Delta is the maximum element frequency. This models for example the degree-bounded spanning-set intersection in two matroids. Finally, we introduce the crossing latticep olyhedron problem, and obtain a (1, b + 2 Delta - 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.