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
  • 325
3 votes
0 answers

Hardness of Approximation for Three Matroid Intersection

I am searching for the best known hardness of approximation bound for three matroid intersection. The input is three matroids on the same ground set which are accessible using three different ...
MatroMan's user avatar
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
  • 325