Delphi.science

Weighted Matroid Intersection under Minimum Rank Oracle

Source: arxiv.org/abs/2611.10701

Taihei Oki

arXivarxiv/2611.10701Nov 7, 2026cs.DMscore 0

We consider matroid intersection under the minimum rank oracle model, in which two matroids are accessible only through an oracle that returns the minimum of the ranks of a given set in the two matroids. By Edmonds' theorem, this oracle determines the matroid intersection polytope, although it does not reveal the exchangeability graphs on which classical algorithms rely. Recent work by Bárász, Bérczi, Király, Oki, Yamaguchi, and Yokoi (2025) showed that unweighted matroid intersection is polynomially solvable in this model. In this paper, we present a strongly polynomial-time algorithm for…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.10701
curl -X POST /api/v1/records/arxiv/2611.10701/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.10701/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'