Cover Image

Approximation Algorithms for Matroid-Intersection Coloring with Applications to Rota's Basis Conjecture

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Arndt, Stephen, Moseley, Benjamin, Pruhs, Kirk, Swamy, Chaitanya, Zlatin, Michael
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Efficiently Coloring the Intersection of a General Matroid and Partition Matroids
by: Arndt, Stephen, et al.
Published: (2025)

Competitive Online Transportation Simplified
by: Arndt, Stephen, et al.
Published: (2025)

A Competitive Algorithm for Throughput Maximization on Identical Machines
by: Moseley, Benjamin, et al.
Published: (2021)

Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints
by: Im, Sungjin, et al.
Published: (2025)

Approximation Algorithms for Steiner Connectivity Augmentation
by: Hathcock, Daniel, et al.
Published: (2023)

Robust Gittins for Stochastic Scheduling
by: Moseley, Benjamin, et al.
Published: (2025)

Polynomial Time Convergence of the Iterative Evaluation of Datalogo Programs
by: Im, Sungjin, et al.
Published: (2023)

An $Ω(n \log n)$ Randomized Lower Bound for Cutting a Cake into Proportionally Fair Pieces
by: Arndt, Stephen, et al.
Published: (2026)

Faster Approximate Linear Matroid Intersection
by: Terao, Tatsuya
Published: (2026)

Approximating Matroid Basis Testing for Partition Matroids using Budget-In-Expectation
by: Hellerstein, Lisa, et al.
Published: (2026)

A Better-Than-2 Approximation for the Directed Tree Augmentation Problem
by: Neuwohner, Meike, et al.
Published: (2025)

Efficient Matroid Intersection via a Batch-Update Auction Algorithm
by: Blikstad, Joakim, et al.
Published: (2024)

On the Parallel Complexity of Finding a Matroid Basis
by: Khanna, Sanjeev, et al.
Published: (2025)

A Weighted-to-Unweighted Reduction for Matroid Intersection
by: Dudeja, Aditi, et al.
Published: (2026)

Deterministic $(2/3-\varepsilon)$-Approximation of Matroid Intersection Using Nearly-Linear Independence-Oracle Queries
by: Terao, Tatsuya
Published: (2024)

Polynomial Kernels with Reachability for Weighted $d$-Matroid Intersection
by: Huang, Chien-Chung, et al.
Published: (2026)

Optimal Verification of a Minimum-Weight Basis in an Uncertainty Matroid
by: Diwan, Haya, et al.
Published: (2025)

Matroid Intersection under Minimum Rank Oracle
by: Bárász, Mihály, et al.
Published: (2024)

Minimizing Completion Times of Stochastic Jobs on Parallel Machines is Hard
by: Moseley, Benjamin, et al.
Published: (2026)

You (Almost) Can't Beat Brute Force for 3-Matroid Intersection
by: Doron-Arad, Ilan, et al.
Published: (2024)

Approximation Algorithms for Correlated Knapsack Orienteering
by: Espinosa, David Aleman, et al.
Published: (2024)

Simultaneously Approximating All $\ell_p$-norms in Correlation Clustering
by: Davies, Sami, et al.
Published: (2023)

Improved Algorithms for Fair Matroid Submodular Maximization
by: Mahabadi, Sepideh, et al.
Published: (2026)

Optimal Parallel Basis Finding in Graphic and Related Matroids
by: Khanna, Sanjeev, et al.
Published: (2025)

Approximation Algorithms for Smallest Intersecting Balls
by: Zheng, Jiaqi, et al.
Published: (2024)

The Online Submodular Assignment Problem
by: Hathcock, Daniel, et al.
Published: (2024)

The Online Submodular Assignment Problem
by: Hathcock, Daniel, et al.
Published: (2024)

Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems
by: Eisenbrand, Friedrich, et al.
Published: (2024)

Faster Global Minimum Cut with Predictions
by: Moseley, Benjamin, et al.
Published: (2025)

Putting Off the Catching Up: Online Joint Replenishment Problem with Holding and Backlog Costs
by: Moseley, Benjamin, et al.
Published: (2024)

Indirect Coflow Scheduling
by: Lindermayr, Alexander, et al.
Published: (2025)

Approximating Submodular Matroid-Constrained Partitioning
by: Bérczi, Kristóf, et al.
Published: (2025)

Almost Tight Additive Guarantees for $k$-Edge-Connectivity
by: Kumar, Nikhil, et al.
Published: (2025)

Better Approximation for Weighted $k$-Matroid Intersection
by: Singer, Neta, et al.
Published: (2024)

Incremental Approximate Single-Source Shortest Paths with Predictions
by: McCauley, Samuel, et al.
Published: (2025)

Unsplittable Cost Flows from Unweighted Error-Bounded Variants
by: Swamy, Chaitanya, et al.
Published: (2025)

FPT Approximation of Generalised Hypertree Width for Bounded Intersection Hypergraphs
by: Lanzinger, Matthias, et al.
Published: (2023)

Incremental Topological Ordering and Cycle Detection with Predictions
by: McCauley, Samuel, et al.
Published: (2024)

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
by: Lee, Euiwoong, et al.
Published: (2024)

Dynamic Matroids: Base Packing and Covering
by: de Vos, Tijn, et al.
Published: (2025)