Abstract:This paper shows a polynomial-time algorithm that, given a general matroid $M_1$ and $k-1$ partition matroids $ M_2, \ldots, M_k$, produces a coloring of the intersection $M = \cap_{i=1}^k M_i$ using at most $1+\sum_{i=1}^k \left(\chi(M_i) -1\right)$ colors. This is the first polynomial-time $O(k)$-approximation algorithm for matroid intersection coloring where one of the matroids may be a general matroid. Leveraging the fact that most of the standard combinatorial matroids reduce to partition matroids at a loss of a factor of two in the chromatic number, this algorithm also yields a polynomial-time $O(k)$-approximation algorithm for matroid intersection coloring in the case where each of the matroids $ M_2, \ldots, M_k$ are one of these standard combinatorial types. Even when $k = 2$, the previous best-known approximation ratio was $O(\log n)$ via a reduction to Set Cover.
From: Stephen Arndt [view email]
[v1]
Tue, 26 Aug 2025 23:26:46 UTC (732 KB)
[v2]
Mon, 13 Jul 2026 07:16:47 UTC (2,310 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。