arXiv:2611.15822 · v1

A Faster Scaling Algorithm for Maximum Weight Matroid Intersection

首次提交 2026-11-12 02:35

版本更新 2026-11-12 02:35

雷达观测 2026-11-13 14:16

摘要

We consider the maximum weight matroid intersection problem. In this problem, we are given two matroids $M_{1}=(E,\mathcal{I}_{1})$ and $M_{2}=(E,\mathcal{I}_{2})$ and integer weights $w(e)$ on the elements $e\in E$, and the goal is to find a maximum-weight common independent set. We give a randomized algorithm that constructs an optimal solution using $\widetilde{O}(nr\log W)$ queries to the independence oracles of the matroids, where $n$ is the size of the ground set $E$, $r$ is the minimum rank of the two matroids, and $W$ is the maximum weight.