Talk:Bounded degree matroid basis

Iterative relaxation -- Tamás Király 09:57, 23 November 2009 (UTC)

There is an example in the paper of Király, Lau and Singh which shows that iterative relaxation does not work here, at least not in the same way as in the spanning tree case. In the example, there is a fully fractional basic solution, but no hyperedge can be removed without the danger of violating the degree bounds by too much. It may be useful to look at similar examples in order to understand better the difficulty of the problem.

New paper on the subject -- Tamás Király 17:27, 22 May 2010 (UTC)

There is a new paper by Bansal et al. that deals with generalizations of the bounded degree matroid basis problem. However, as far as I can see, they do not answer this particular question.