Bounded degree matroid basis
Statement
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 () be lower and upper bounds on the hyperedges. Let OPT denote the minimum cost of a basis B of M which satisfies for every . Is there a polynomial algorithm to find a basis B such that and ?
Record
- Source
- Added
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.