Image de couverture de livre

A Weighted-to-Unweighted Reduction for Matroid Intersection

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Dudeja, Aditi, Grilnberger, Mara
Format:	Preprint
Publié:	2026
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Dynamic Matroids: Base Packing and Covering
par: de Vos, Tijn, et autres
Publié: (2025)

A Note on Rounding Matchings in General Graphs
par: Dudeja, Aditi
Publié: (2024)

Adaptive Fully Dynamic $k$-Center Clustering with (Near-)Optimal Worst-Case Guarantees
par: Grilnberger, Mara, et autres
Publié: (2026)

Matching Composition and Efficient Weight Reduction in Dynamic Matching
par: Bernstein, Aaron, et autres
Publié: (2024)

Polynomial Kernels with Reachability for Weighted $d$-Matroid Intersection
par: Huang, Chien-Chung, et autres
Publié: (2026)

From Unweighted to Weighted Dynamic Matching in Non-Bipartite Graphs: A Low-Loss Reduction
par: Bernstein, Aaron, et autres
Publié: (2025)

Efficiently Coloring the Intersection of a General Matroid and Partition Matroids
par: Arndt, Stephen, et autres
Publié: (2025)

Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
par: Nogler, Jakob, et autres
Publié: (2024)

Faster Approximate Linear Matroid Intersection
par: Terao, Tatsuya
Publié: (2026)

Randomized Greedy Online Edge Coloring Succeeds for Dense and Randomly-Ordered Graphs
par: Dudeja, Aditi, et autres
Publié: (2024)

Matroid Intersection under Minimum Rank Oracle
par: Bárász, Mihály, et autres
Publié: (2024)

Approximation Algorithms for Matroid-Intersection Coloring with Applications to Rota's Basis Conjecture
par: Arndt, Stephen, et autres
Publié: (2026)

Efficient Matroid Intersection via a Batch-Update Auction Algorithm
par: Blikstad, Joakim, et autres
Publié: (2024)

You (Almost) Can't Beat Brute Force for 3-Matroid Intersection
par: Doron-Arad, Ilan, et autres
Publié: (2024)

Revoke vs. Restart in Unweighted Throughput Scheduling
par: He, Changdao
Publié: (2025)

Optimal Verification of a Minimum-Weight Basis in an Uncertainty Matroid
par: Diwan, Haya, et autres
Publié: (2025)

Distributed Stochastic Graph Algorithms
par: Censor-Hillel, Keren, et autres
Publié: (2026)

Frontier Space-Time Algorithms Using Only Full Memory
par: Chmel, Petr, et autres
Publié: (2026)

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

Unweighted One-Sided Code Sparsifiers and Thin Subgraphs
par: Gharan, Shayan Oveis, et autres
Publié: (2025)

Better Approximation for Weighted $k$-Matroid Intersection
par: Singer, Neta, et autres
Publié: (2024)

Approximating Matroid Basis Testing for Partition Matroids using Budget-In-Expectation
par: Hellerstein, Lisa, et autres
Publié: (2026)

An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs
par: Brewer, Bruce W., et autres
Publié: (2025)

Unsplittable Cost Flows from Unweighted Error-Bounded Variants
par: Swamy, Chaitanya, et autres
Publié: (2025)

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
par: Lee, Euiwoong, et autres
Publié: (2024)

Matroid Secretary via Labeling Schemes
par: Bérczi, Kristóf, et autres
Publié: (2024)

Sample-Based Matroid Prophet Inequalities
par: Fu, Hu, et autres
Publié: (2024)

The $k$-Fold Matroid Secretary Problem
par: Gujjar, Rishi, et autres
Publié: (2025)

Unweighted Geometric Hitting Set for Line-Constrained Disks and Related Problems
par: Liu, Gang, et autres
Publié: (2024)

Improved Algorithms for Fair Matroid Submodular Maximization
par: Mahabadi, Sepideh, et autres
Publié: (2026)

Multiagent Matroid Upgrading: Greedy is Fair and Efficient
par: Ma, Qingwen, et autres
Publié: (2026)

On the Parallel Complexity of Finding a Matroid Basis
par: Khanna, Sanjeev, et autres
Publié: (2025)

Efficient Classical Sampling from Gaussian Boson Sampling Distributions on Unweighted Graphs
par: Zhang, Yexin, et autres
Publié: (2025)

Unweighted Layered Graph Traversal: Passing a Crown via Entropy Maximization
par: Bai, Xingjian, et autres
Publié: (2024)

Subquadratic Submodular Maximization with a General Matroid Constraint
par: Kobayashi, Yusuke, et autres
Publié: (2024)

Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints
par: Inamdar, Tanmay, et autres
Publié: (2024)

Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems
par: Eisenbrand, Friedrich, et autres
Publié: (2024)

Beating Competitive Ratio 4 for Graphic Matroid Secretary
par: Banihashem, Kiarash, et autres
Publié: (2025)

Matroid-Based TSP Rounding for Half-Integral Solutions
par: Gupta, Anupam, et autres
Publié: (2021)

Fixed-Parameter Tractable Submodular Maximization over a Matroid
par: Nematollahi, Shamisa, et autres
Publié: (2025)