Bounded degree matroid basis

From Egres Open
Jump to: navigation, search

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]?


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].


  1. M. Singh, L. C. Lau, Approximating minimum bounded degree spanning trees to within one of optimal, DOI link, author link
  2. 2.0 2.1 T. Király, L. C. Lau, M. Singh, Degree Bounded Matroids and Submodular Flows, DOI link, author link
  3. N. Bansal, R. Khandekar, V. Nagarajan, Additive guarantees for degree bounded directed network design, DOI link, author link
  4. N. Bansal, R. Khandekar, J. Könemann, V. Nagarajan, B. Peis, On Generalizations of Network Design Problems with Degree Bounds, DOI link arXiv link