On generalizations of network design problems with degree bounds (Q378106): Difference between revisions

It is well known that the degree bounded minimum spanning tree problem is NP-hard. But \textit{M. Singh} and \textit{L. Chi Lau} [Proceedings of the 39th annual ACM symposium on theory of computing, San Diego, CA, USA, 2007. New York, NY: Association for Computing Machinery (ACM). 661--670 (2007; Zbl 1232.68184)] used an iterative relaxation technique to provide a polynomial time algorithm giving a spanning tree of at most optimum cost and with the degree violation at most 1. The main result of this paper is a generalization of the result to the so-called laminar minimum crossing spanning tree (MCST) problem. In that problem, an edge- weighted undirected graph with a laminar family \(\{S_i\}_{i=1}^m\) of vertex sets having bounds \(\{b_i\}_{i=1}^m\) (laminar means that if \(S_i\cap S_j\neq \emptyset\) then \(S_i\subseteq S_j\) or \(S_j\subseteq S_i\)) is given. The task is to find a spanning tree of minimum costs that contains at most \(b_i\) edges from \(\{(u,v)| u\in S_i, v\notin S_i\}\) for each \(i\). The authors provide a polynomial time algorithm for this problem giving the degree violation at most \(O(\log n)\). On the other hand, they show the additive inapproximability of the general MCST problem with degree violation at most \(O(\log^c m)\) for some constant \(c>0\). Degree bounds are also incorporated in other combinatorial optimization problems, such as matroid intersection and lattice polyhedra, and also integrality gaps for these problems are studied.