Cover Image

Dynamic Matroids: Base Packing and Covering

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	de Vos, Tijn, Grilnberger, Mara
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity
by: de Vos, Tijn, et al.
Published: (2024)

Adaptive Fully Dynamic $k$-Center Clustering with (Near-)Optimal Worst-Case Guarantees
by: Grilnberger, Mara, et al.
Published: (2026)

Distributed Sparsest Cut via Eigenvalue Estimation
by: Maus, Yannic, et al.
Published: (2025)

Towards Constant Time Multi-Call Rumor Spreading on Small-Set Expanders
by: Cruciani, Emilio, et al.
Published: (2025)

Deterministic Edge Coloring with few Colors in CONGEST
by: Blikstad, Joakim, et al.
Published: (2026)

New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
by: Dory, Michal, et al.
Published: (2022)

Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances
by: Brand, Jan van den, et al.
Published: (2025)

Sample-Based Matroid Prophet Inequalities
by: Fu, Hu, et al.
Published: (2024)

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

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

Matroid-Based TSP Rounding for Half-Integral Solutions
by: Gupta, Anupam, et al.
Published: (2021)

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

The Power of Migrations in Dynamic Bin Packing
by: Mellou, Konstantina, et al.
Published: (2024)

Distributed Santa Claus via Global Rounding
by: de Vos, Tijn, et al.
Published: (2026)

The $k$-Fold Matroid Secretary Problem
by: Gujjar, Rishi, et al.
Published: (2025)

Matroid Secretary via Labeling Schemes
by: Bérczi, Kristóf, et al.
Published: (2024)

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

Fault-Tolerant Matroid Bases
by: Bentert, Matthias, et al.
Published: (2025)

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

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

Multiagent Matroid Upgrading: Greedy is Fair and Efficient
by: Ma, Qingwen, et al.
Published: (2026)

Fully Dynamic Submodular Maximization over Matroids
by: Dütting, Paul, et al.
Published: (2023)

Beating Competitive Ratio 4 for Graphic Matroid Secretary
by: Banihashem, Kiarash, et al.
Published: (2025)

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

Subquadratic Submodular Maximization with a General Matroid Constraint
by: Kobayashi, Yusuke, et al.
Published: (2024)

Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints
by: Inamdar, Tanmay, et al.
Published: (2024)

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

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

Fixed-Parameter Tractable Submodular Maximization over a Matroid
by: Nematollahi, Shamisa, et al.
Published: (2025)

Lower Bounds for Matroid Optimization Problems with a Linear Constraint
by: Doron-Arad, Ilan, et al.
Published: (2023)

The Traveling Tournament Problem: Improved Algorithms Based on Cycle Packing
by: Zhao, Jingyang, et al.
Published: (2024)

Green Bin Packing
by: Bibbens, Jackson, et al.
Published: (2025)

Packing Short Cycles
by: Bentert, Matthias, et al.
Published: (2024)

Sampling Sphere Packings with Continuum Glauber Dynamics
by: Kuchukova, Aiya, et al.
Published: (2026)

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

Approximation Algorithms for Matroid-Intersection Coloring with Applications to Rota's Basis Conjecture
by: Arndt, Stephen, et al.
Published: (2026)

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

The Support of Bin Packing is Exponential
by: Jansen, Klaus, et al.
Published: (2025)

Solving Co-Path/Cycle Packing and Co-Path Packing Faster Than $3^k$
by: Liu, Yuxi, et al.
Published: (2024)