CS Paper Radar

Weighted Equitability and Matroid-Constrained Discrepancy

Kristóf Bérczi, Siyue Liu, Victor Reis, Jakub Tarnawski

cs.DS ·submitted 2026-08-14 05:56 UTC · v1
theory

Abstract

We prove weighted matroid equitability. Let $M=(E,\mathcal{I})$ be a matroid whose ground set can be partitioned into $k$ bases, and assign a nonnegative weight to every element. Then $E$ has a partition into $k$ bases such that the weights of any two bases differ by at most the largest element weight. We present two proofs based on the localized exchange theorem of Akrami, Liu, Raj, and Végh. The first is existential, while the second is constructive and leads to a strongly polynomial-time algorithm. As applications, we obtain an additive guarantee for matroid-constrained makespan minimization for identical machines and a strongly polynomial-time algorithm for finding an EF1 allocation under a matroid constraint and identical additive valuations. We further generalize the Beck--Fiala framework in discrepancy theory to settings with matroid constraints. Given a nonnegative matrix of column sparsity $Δ$, we show that a fractional basis can be rounded to a basis of no larger cost while preserving every row sum within additive error $2Δ$ times the largest matrix entry. Motivated by the $2$-sparse prefix Beck--Fiala conjecture, we formulate a conjecture on prefix-constrained matroid bases and prove a discrepancy bound $O(\log n)$. Finally, we give a counterexample to the weighted carpooling conjecture, thereby also disproving a conjecture by Morell and Skutella on single-source unsplittable flows with two-sided discrepancy bounds.

Closest papers

Nearest neighbours by meaning across the whole index.

Constrained Fair Allocations via Partition Matroid Reductions

cs.GT ·2026-08-31 ·Benjamin Cookson, Nisarg Shah
published similarity 0.75
Abstract · Accepted to ACM EAAMO 2026

We study fair allocation of indivisible goods under additive valuations and matroid constraints. A challenging open question is whether a complete and feasible envy-free up to one good (EF1) allocation exists under every matroid that admits a complete and feasible allocation. The state-of-the-art result by Biswas and Barman [2018] positively resolves this question for partition matroids. Our first result positively resolves it for laminar matroids, which generalize partition matroids, when there are three agents. Our technique reduces this general existence question to finding an EF1 allocation satisfying a mild additional condition under a single finite-sized key laminar matroid, and we establish the required allocation by case analysis. We show that our technique somewhat extends to four agents, reducing the analogous problem to finding EF1 allocations under two finite-sized laminar matroids, although we are unable to establish their existence. We also use recent matroid decomposition results to establish EF1 existence under broader classes of matroids. Specifically, we show that EF1 allocations always exist under transversal matroids whenever a complete allocation is feasible, and obtain existence results for graphic matroids and gammoids under stronger assumptions.

0.48

Tight Approximation Results for Matroid Optimization with a Linear Constraint

cs.DS ·2026-09-23 ·Ilan Doron-Arad, Hadas Shachnai, Gilad Shmerler
similarity 0.74
Abstract

We study the following class of matroid optimization problems with a linear constraint (P-MOL). Given a matroid M=(E,I), two weight functions $v,w:E\to R_{\ge 0}$, and a threshold $L\in R_{\ge 0}$, find $opt v(S)$ where S is either an independent set or a base of M satisfying a budget-type constraint: $w(S)\le L$ or $w(S)\ge L$, and $opt\in\{min,max\}$. P-MOL provides a unified representation for a broad family of NP-hard optimization problems, including budgeted matroid independent set, constrained minimum-basis, and knapsack-cover variants with a matroid constraint. Also, it naturally extends to multiple matroid constraints. In particular, we consider the matroid intersection cover (MIC) problem, where feasibility is defined by the common independent sets of two matroids and one seeks minimum $v(S)$ subject to $w(S)\ge L$. Our main result is a unified EPTAS for all nontrivial P-MOL variants, obtained by generalizing a technique of Hassin and Levin (SIAM J. Comput., 2004) for solving the constrained minimum spanning tree problem. Specifically, for any fixed $ε>0$, we present an algorithm running in time $|E|^{O(1)} (1/{ε^2})^{O(1/ε)}$ that outputs a feasible solution S whose value is at most $(1+ε)OPT$ for minimization variants and at least $(1-ε)OPT$ for maximization variants. This resolves the complexity status of all members of P-MOL, as none of these problems admits an FPTAS (Doron-Arad, Kulik and Shachnai, ICALP'24). Finally, we separate the P-MOL family from its extension to matroid intersection. We show that an EPTAS is unlikely to exist for the matroid intersection variant of P-MOL under a covering constraint, whereas an EPTAS is known to exist under a budget constraint. This highlights a qualitative difference between these two types of linear constraints that does not arise in the single-matroid setting.

0.14

When Elements Fail: Weighted Fault-Tolerant Matroid Bases

cs.DS cs.DM ·2026-11-12 ·Madhumita Kundu, Soumi Nandi, Saket Saurabh
similarity 0.72
Abstract

Given a rank-\(r\) matroid on \(n\) elements with nonnegative costs and a partition into safe and vulnerable elements, we seek a minimum-cost set that spans after every deletion of at most \(k\) selected vulnerable elements. We resolve several open questions posed by Bentert, Fomin, Golovach, and Morelle (ESA 2025) concerning weighted costs, nonuniform failures, and explicitly specified failure scenarios. To this end, we develop two compression methods. For matroids given by an independence oracle, weighted flat-avoidance representatives yield a bounded subset of the ground set containing an optimal solution and a \(2^{\mathcal{O}((r+k)^4)}n^{\mathcal{O}(1)}\)-time algorithm. This establishes fixed-parameter tractability for weighted costs and nonuniform failures simultaneously. For explicitly represented linear matroids, polynomial certificates allow us to compress families of partial solutions while preserving successful completions under all allowed failures. This yields a deterministic algorithm using \(2^{\mathcal{O}(kr(r+k)\log(r+1))}n^{\mathcal{O}(1)}\) field operations over arbitrary fields. Over fixed finite fields, a simpler reduction uses parallel classes. For explicitly listed failure scenarios, we obtain fixed-parameter algorithms parameterized by rank and the number of scenarios. In contrast, the size-budget decision version is W[1]-hard parameterized by rank and maximum scenario size, even on uniform matroids with two-element scenarios. \keywords{Matroids \and Fault tolerance \and Fixed-parameter algorithms \and Representative families}

0.20

Stronger Hardness for Submodular Maximization Subject to a Matroid Constraint

cs.DS ·2026-10-05 ·Moran Feldman, Alan Kuhnle
similarity 0.69
Abstract · 13 pages. This version adds a remark about the relationship between this work and the results of arXiv:2610.00545

Maximizing a submodular function subject to a matroid constraint is a cornerstone problem in combinatorial optimization. The state-of-the-art algorithm for this problem obtains $0.401$-approximation~\cite{buchbinder2024constrained}, and the state-of-the-art hardness result shows that no polynomial time algorithm can obtain better than $0.478$-approximation for this problem~\cite{oveisgharan2011submodular}. In this work, we present the first improvement in $15$ years for the hardness result, showing that no polynomial time algorithm in the value-oracle model can obtain better than $8/17 \approx 0.471$-approximation, even for the special case of a cardinality or (simplified) partition matroid constraint.

0.40

The Strong Secretary Conjecture is True for Linear Matroids

cs.DS ·2026-09-17 ·Kristóf Bérczi, Shaddin Dughmi, Vasilis Livanos, José A. Soto, Victor Verdugo
theory similarity 0.69
Abstract

We prove a $1/e$ guarantee for Matroid Secretary on linear matroids: each element of a fixed optimal basis is selected with probability at least $1/e$. This settles the strong secretary conjecture for this class of matroids. Our result holds both when the matroid is known in advance and when a linear representation is given online. In the known-matroid model, the result extends to fully modular extendable matroids. We also obtain $1/e$ guarantees for a more general model on linear matroids, both when the matroid is known and when its representation is revealed online. In XOS Matroid Secretary, agents with XOS valuations over the elements arrive in uniformly random order, and the algorithm must assign each arriving agent a bundle of elements. The bundles must be pairwise disjoint, and their union must be an independent set of the matroid. We obtain an expected total value of at least $1/e$ times the offline optimum. This model contains Group Matroid Secretary, in which the elements are adversarially partitioned into groups that arrive in uniformly random order, and the algorithm selects a subset of each arriving group. For this special case, we select each element of a fixed optimal basis with probability at least $1/e$

0.44

A Faster Auction Algorithm for Weighted Matroid Intersection

cs.DS ·2026-10-01 ·Tatsuya Terao
similarity 0.69
Abstract · 17 pages. In this version, we have completely rewritten the proof, which is now simpler and easier to follow, and improved the clarity and p…

We consider the weighted matroid intersection problem in the independence-oracle model. A sequence of works by Huang--Kakimura--Kamiyama~[SODA'16 \& Math. Program'19], Chekuri--Quanrud~[SODA'16], Quanrud~[ICALP'24], and Dudeja--Grilnberger~[IPCO'26] has developed efficient $(1-\varepsilon)$-approximation algorithms for this problem. We present a simple deterministic auction algorithm that, given two matroids on a common ground set of size $n$, computes a $(1-\varepsilon)$-approximate maximum-weight common independent set using $O(n \varepsilon^{-2} \log^2(n))$ independence-oracle queries. This is the first deterministic $(1-\varepsilon)$-approximation algorithm for the weighted matroid intersection problem whose query complexity is nearly linear in $n$ and polynomial in $1/\varepsilon$. Our algorithm builds on the auction algorithm for unweighted matroid intersection by Huang--Kobayashi~['26].

0.28

On the Strong Matroid Secretary Conjecture and Beyond

cs.DS ·2026-09-16 ·Hamed Abdi, Kiarash Banihashem, MohammadTaghi Hajiaghayi, Danny Mittal
theoryhot directionhighly cited similarity 0.68
Abstract

The strong matroid secretary conjecture asserts that every matroid admits a $1/e$-competitive secretary algorithm, matching the classical single-choice guarantee. We formulate a finite linear program whose value is the optimal ordinal competitive ratio of any fixed matroid; for all matroids of positive rank on seven elements and nearly all on eight, this value exceeds $1/e$. The same computations suggested that the optimal ratio is monotone under truncation of the matroid; we prove this for uniform matroids, where the ratio is strictly increasing in the rank, and refute it for a graphic matroid. Guided by this evidence, we prove the conjecture for every linear matroid, a class that includes graphic matroids, regular matroids, laminar matroids, and gammoids, giving a $1/e$-competitive ordinal secretary algorithm. The algorithm maintains bounds on the expected intersection dimension of the accepted span with every ambient subspace. Uncrossing and separation show that these bounds can be preserved while admitting each current greedy-basis element with a prescribed probability and the construction uses finite linear programs. For every matroid, we also give a single-sample prophet algorithm with competitive ratio $1/2$ in any fixed arrival order independent of the samples and values. Its output, including the selected values, has exactly the law of an independent fair thinning of an optimum from a fresh product draw. The algorithm uses $O(n^2)$ independence queries on $n$ elements. Both constants are tight in their respective models. We also give a self-contained black-box reduction that converts a single-sample prophet ratio $α$ into a secretary ratio $α^2/16$, preserving polynomial running time. Our single-sample algorithm consequently yields a $1/64$-competitive ordinal secretary algorithm for arbitrary matroids.

0.46

Weighted Matroid Intersection under Minimum Rank Oracle

cs.DM math.COmath.OC ·2026-11-07 ·Taihei Oki
theory similarity 0.68
Abstract

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 weighted matroid intersection in this model. The key to our algorithm is a polynomial-size extended formulation of tangent cones of common base polytopes that can be constructed using the minimum rank oracle. We also give min-max theorems in terms of the minimum rank function via 1/3-submodularity, and present a strongly polynomial-time algorithm to compute an optimal dual solution.

0.14