Questions tagged [matroids]
The matroids tag has no usage guidance.
3
questions
4
votes
0
answers
70
views
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 ...
- 173
1
vote
1
answer
159
views
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 ...
- 173
0
votes
0
answers
56
views
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 ...
- 2,086