<p>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 memebership oracles, and the objective is to find a maximum sized set S which is independent in all three matroids.</p>
<p>The problem has a two approximation (see &quot;Iterative Methods in Combinatorial Optimization&quot; by Lau, Ravi and Singh, page 83). The problem also generalizes three-dimensional matching and therefore is, in some sense, APX-hard.</p>
<p>The question is what is the best hardness of approximation result known for the problem? Also, is there an hardness of approximation result which relies on the oracle model and does not use a complexity related assumption?</p>

CC BY-SA 4.0
2024-02-24T17:13:00.153Z
What are some examples of 3- Metroid intersection?  E.g. can you do longest path?
Neal Young
CC BY-SA 4.0
2024-02-26T20:54:14.363Z
@NealYoung A nice example is hamiltonian cycle on a directed graph:  the ground set of the matroids is the edges of the graph. One matroid is the graphic matroid of the graph G, a second matroid ensures the in-degree of every vertex is at most 1, and a third matroid ensures the out-degree of every vertex is at most 1. There is a size n solution if and only if there is an hamiltonian cycle.
MatroMan
CC BY-SA 4.0
2024-02-27T14:33:46.303Z
Interesting.  I assume you mean "hamiltonian path" instead of "hamiltonian cycle"?  And if you take, say, a 2-approximation to the maximum in the 3-matroid intersection you describe, can you somehow use it to get any approximation for longest path?
Neal Young
CC BY-SA 4.0
2024-02-28T19:56:56.457Z
To answer my own question, it looks like (i) a set is in the 3-intersection iff it is a collection of vertex-disjoint paths, and (ii) a 2-approximation to a maximum-size such set is obtained by any maximum matching (and this is computable in P).  A maximum matching doesn't seem to help much in approximating a longest path.
Neal Young
<optimization><approximation-hardness><matroids>
Hardness of Approximation for Three Matroid Intersection
MatroMan
# Hardness of Approximation for Three Matroid Intersection

(Asked by: username_0 on 2024-02-22)

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 memebership oracles, and the objective is to find a maximum sized set S which is independent in all three matroids.

The problem has a two approximation (see "Iterative Methods in Combinatorial Optimization" by Lau, Ravi and Singh, page 83). The problem also generalizes three-dimensional matching and therefore is, in some sense, APX-hard.

The question is what is the best hardness of approximation result known for the problem? Also, is there an hardness of approximation result which relies on the oracle model and does not use a complexity related assumption?

**Tags:** optimization, approximation-hardness, matroids

> **Comments:**
> **username_1**: What are some examples of 3- Metroid intersection?  E.g. can you do longest path?  
> **username_0**: @NealYoung A nice example is hamiltonian cycle on a directed graph:  the ground set of the matroids is the edges of the graph. One matroid is the graphic matroid of the graph G, a second matroid ensures the in-degree of every vertex is at most 1, and a third matroid ensures the out-degree of every vertex is at most 1. There is a size n solution if and only if there is an hamiltonian cycle.  
> **username_1**: Interesting.  I assume you mean "hamiltonian path" instead of "hamiltonian cycle"?  And if you take, say, a 2-approximation to the maximum in the 3-matroid intersection you describe, can you somehow use it to get any approximation for longest path?  
> **username_1**: To answer my own question, it looks like (i) a set is in the 3-intersection iff it is a collection of vertex-disjoint paths, and (ii) a 2-approximation to a maximum-size such set is obtained by any maximum matching (and this is computable in P).  A maximum matching doesn't seem to help much in approximating a longest path.  

---

## 0 answers

