Cover Image

Multiagent Matroid Upgrading: Greedy is Fair and Efficient

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Ma, Qingwen, Peng, Chao, Xu, Changfeng, Xu, Chenyang, Zhang, Ruilong
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

Logarithmic Approximations for Fair k-Set Selection
by: Li, Shi, et al.
Published: (2025)

Fair Submodular Maximization over a Knapsack Constraint
by: Li, Lijun, et al.
Published: (2025)

Polylogarithmic Approximation for Robust s-t Path
by: Li, Shi, et al.
Published: (2023)

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

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

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

Laminar Matroid Secretary: Greedy Strikes Back
by: Huang, Zhiyi, et al.
Published: (2023)

Potential-Based Greedy Matching for Dynamic Delivery Pooling
by: Ma, Hongyao, et al.
Published: (2025)

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

On the Congruency-Constrained Matroid Base
by: Liu, Siyue, et al.
Published: (2023)

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

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

Greedy Dynamic Matching
by: Arnosti, Nick, et al.
Published: (2025)

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

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

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

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

New Greedy Spanners and Applications
by: Popova, Elizaveta, et al.
Published: (2026)

A Lossless Deamortization for Dynamic Greedy Set Cover
by: Solomon, Shay, et al.
Published: (2024)

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

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

Public Event Scheduling with Busy Agents
by: Li, Bo, et al.
Published: (2024)

Greedy BST on Permutation Initial Tree
by: Pareek, Akash
Published: (2024)

From Dynamic Programs to Greedy Algorithms
by: van Melkebeek, Dieter
Published: (2025)

Efficient Greedy Discrete Subtrajectory Clustering
by: van der Hoog, Ivor, 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)

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

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

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

Robust Multiagent Collaboration Through Weighted Max-Min T-Joins
by: Alipour, Sharareh
Published: (2026)

Engineering Algorithms for Dynamic Greedy Set Cover
by: Uzrad, Amitai
Published: (2026)

Greedy Completion for Weighted $(α,β)$-Spanners
by: Tzalik, Elad
Published: (2026)

An Improved Greedy Approximation for (Metric) $k$-Means
by: Charikar, Moses, et al.
Published: (2026)

Efficient Approximation Algorithms for Fair Influence Maximization under Maximin Constraint
by: Rui, Xiaobin, et al.
Published: (2025)

Efficient Branch-and-Bound for Submodular Function Maximization under Knapsack Constraint
by: Hao, Yimin, et al.
Published: (2025)

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 Power of Greedy for Online Minimum Cost Matching on the Line
by: Balkanski, Eric, et al.
Published: (2022)