Questions tagged [matroids]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
4 votes
0 answers

distinguishments between query complexity of membership oracles and standard time complexity

Many combinatorial optimization problems can be described as follows. We are given a set system $(E,I)$, where $I \subseteq 2^E$ and a weight function $w: E \rightarrow \mathbb{N}$. The goal is to ...
John's user avatar
  • 173
1 vote
1 answer

3 Matroid Intersection, a Special Case

It is well known that finding a maximum cardinality (or weight) common independent set in the intersection of 3 matroids is APX-Hard. Question: Does this problem remain NP-Hard if one of the matroids ...
John's user avatar
  • 173
0 votes
0 answers

Maximum-weight matroid intersection with real weights

Given a matroid with weighted elements, a basis with maximum total weight can be found in polynomial time using the greedy algorithm. This is true even when the weights are real numbers, if we assume ...
Erel Segal-Halevi's user avatar