{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreidmi3s7zzvxxrepba7xujvkbn4mkqi6szyivr5snhtvhdnobjieve",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mf4alveyqad2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.15702v1",
  "publishedAt": "2026-02-18T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Aditi Dudeja",
    "Mara Grilnberger"
  ],
  "textContent": "**Authors:** Aditi Dudeja, Mara Grilnberger\n\nGiven two matroids $\\mathcal{M}_1$ and $\\mathcal{M}_2$ over the same ground set, the matroid intersection problem is to find the maximum cardinality common independent set. In the weighted version of the problem, the goal is to find a maximum weight common independent set. It has been a matter of interest to find efficient approximation algorithms for this problem in various settings. In many of these models, there is a gap between the best known results for the unweighted and weighted versions. In this work, we address the question of closing this gap. Our main result is a reduction which converts any $α$-approximate unweighted matroid intersection algorithm into an $α(1-\\varepsilon)$-approximate weighted matroid intersection algorithm, while increasing the runtime of the algorithm by a $\\log W$ factor, where $W$ is the aspect ratio. Our framework is versatile and translates to settings such as streaming and one-way communication complexity where matroid intersection is well-studied. As a by-product of our techniques, we derive new results for weighted matroid intersection in these models.",
  "title": "A Weighted-to-Unweighted Reduction for Matroid Intersection"
}