Bounded degree matroid basis
Let M be a matroid on ground set V, let H=(V,E) be a hypergraph with maximum degree [math]\Delta[/math], let c(v) be the cost of node v, and let [math]l(e) \leq u(e)[/math] ([math]e \in E[/math]) be lower and upper bounds on the hyperedges. Let OPT denote the minimum cost of a basis B of M which satisfies [math]l(e) \leq |B \cap e| \leq u(e)[/math] for every [math]e \in E[/math]. Is there a polynomial algorithm to find a basis B such that [math]c(B) \leq OPT[/math] and [math]l(e)-\Delta+1 \leq |B \cap e| \leq u(e)+\Delta-1[/math]?
Remarks
This would be a generalization of the result of Lau and Singh [1] on the bounded degree spanning tree problem. If there are only upper bounds on all hyperedges or there are only lower bounds on all hyperedges, then there is a polynomial algorithm, see Király, Lau, and Singh [2] and Bansal, Khandekar, and Nagarajan [3]. However, if both upper and lower bounds are present, then the best known result for general matroids gives [math]l(e)-2\Delta+1 \leq |B \cap e| \leq u(e)+2\Delta-1[/math] [2].
An extension of the above results to lattice polyhedra has recently been given by Bansal et al. [4].
References
- ↑ M. Singh, L. C. Lau, Approximating minimum bounded degree spanning trees to within one of optimal, DOI link, author link
- ↑ 2.0 2.1 T. Király, L. C. Lau, M. Singh, Degree Bounded Matroids and Submodular Flows, DOI link, author link
- ↑ N. Bansal, R. Khandekar, V. Nagarajan, Additive guarantees for degree bounded directed network design, DOI link, author link
- ↑ N. Bansal, R. Khandekar, J. Könemann, V. Nagarajan, B. Peis, On Generalizations of Network Design Problems with Degree Bounds, DOI link arXiv link
