The integrality gap of weighted -matroid intersection
Weighted -matroid intersection asks for a maximum-weight set independent in each of matroids on a common ground set. The natural linear-programming relaxation optimises over the intersection of the matroid independence polytopes, and its integrality gap is conjectured to be at most . That is known for ; for the best general upper bound was . Lee, Sviridenko and Vondrák conjectured further that for weighted -matchoids the gap is exactly . How large is the gap?
- Result
- Proved(see note)
- Status
- Partial result
- AI contribution
- AI-assisted
- Method
- Argument
- Field
- Approximation algorithms; matroid optimisation
- Posed by
- The $k-1$ bound is the standard conjecture for $k$-matroid intersection; the $p-1+1/p$ form for weighted $p$-matchoids is Conjecture 1 of Lee, Sviridenko and Vondrák
- Year posed
- —
- Years open
- —
- Solved
- 2026-09-18
- Model
- GPT-5.6 Sol
- Vendor
- OpenAI
- Collaborators
- Yu Cong, Yajie Zhao
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 20 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Partial on the headline conjecture, complete on a named part of another. For weighted -matroid intersection the integrality gap is at most , improving the previous general bound of but not reaching the conjectured . For weighted -matchoids the gap is at most , with a deterministic LP-relative algorithm achieving the same factor; the paper states that this resolves the -matchoid part of Lee, Sviridenko and Vondrák's Conjecture 1, and projective planes of order give tight instances whenever one exists.
What the AI did
From the paper's AI Disclosure: the authors used GPT-5.6 Sol to assist with developing the integrality-gap proof and deriving the local-ratio algorithm.
Verification
Checked here on 27 September 2026 against arXiv:2609.21477, posted 18 September. The abstract and introduction were read: the -matroid bound improves from to , short of the conjectured , and the -matchoid result attains with a deterministic LP-relative algorithm, which the paper says resolves the -matchoid part of Lee, Sviridenko and Vondrák's Conjecture 1, projective planes of order giving tight instances where one exists. The AI Disclosure is one sentence and is quoted in the AI role field. The mathematics was not checked here; nine days old, no referee, no formalisation.
Source
Submitted by AmberWombat684 on