On generalizations of network design problems with degree bounds (Q378106)

From MaRDI portal
scientific article; zbMATH DE number 5724200
  • On Generalizations of Network Design Problems with Degree Bounds
Language Label Description Also known as
English
On generalizations of network design problems with degree bounds
scientific article; zbMATH DE number 5724200
  • On Generalizations of Network Design Problems with Degree Bounds

Statements

On generalizations of network design problems with degree bounds (English)
0 references
On Generalizations of Network Design Problems with Degree Bounds (English)
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
11 November 2013
0 references
22 June 2010
0 references
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.
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
spanning tree
0 references
degree bound
0 references
approximation algorithm
0 references
network model
0 references
network design
0 references
graphic algorithms
0 references
analysis of algorithms
0 references
matroid intersection
0 references
lattice polyhedron
0 references
0 references
0 references
0 references