The weighted 
-matroid
intersection problem asks for a maximum-weight subset
of a common ground set that is independent in each
of 
given matroids. Edmonds (1979) showed that the case 
can be solved in polynomial
time. For 
,
a natural linear programming relaxation intersects
the independent-set polytopes of the 
matroids. Its integrality gap
is the largest possible ratio of the fractional optimum to the weight of a maximum
common independent set.
The integrality gap is conjectured to be at most 
. This is known for 
. The previous general upper bound for 
was 
. Cong and Zhao (2026) reported the improved bound
 |
They also reported that the natural relaxation for a 
-matchoid, in which each element belongs to at most 
local matroid ground
sets, has integrality gap at most 
, with a deterministic algorithm
attaining that factor. Projective planes of order
,
when they exist, give equality. The latter result resolves the 
-matchoid part of a conjecture of Lee, Sviridenko, and Vondrák,
while the conjectured 
bound for intersections of global matroids
remains open.
GPT-5.6 Sol reportedly assisted with the integrality-gap proof and the local-ratio algorithm, which the authors verified. As of Sep. 27, 2026, independent specialist review had not been reported.
