# 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