Bounded degree matroid basis
Let M be a matroid on ground set V, let H=(V,E) be a hypergraph with maximum degree Δ, let c(v) be the cost of node v, and let l(e)≤u(e) (e∈E) be lower and upper bounds on the hyperedges. Let OPT denote the minimum cost of a basis B of M which satisfies l(e)≤|B∩e|≤u(e) for every e∈E. Is there a polynomial algorithm to find a basis B such that c(B)≤OPT and l(e)−Δ+1≤|B∩e|≤u(e)+Δ−1?
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 l(e)−2Δ+1≤|B∩e|≤u(e)+2Δ−1 [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
