Matroid intersection concerns subsets independent in each of several matroids. 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.
The counting problem is distinct from finding a maximum common independent set. Chen and Liu (2026) gave a fully polynomial-time randomized approximation scheme for the number of common matroid bases of two matroids on the same ground set, accessed by independence oracles. They also obtained approximately uniform sampling in polynomial time. Chen and Liu (2026) state that GPT-5.6 Sol Ultra and GPT-6 Astra Ultra were heavily used in developing the ideas.
