Imagen de Portada

Efficient Matroid Intersection via a Batch-Update Auction Algorithm

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Blikstad, Joakim, Tu, Ta-Wei
Formato:	Preprint
Publicado:	2024
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Maximum Flow by Augmenting Paths in $n^{2+o(1)}$ Time
por: Bernstein, Aaron, et al.
Publicado: (2024)

Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs
por: Bernstein, Aaron, et al.
Publicado: (2025)

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

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

Deterministic Online Bipartite Edge Coloring
por: Blikstad, Joakim, et al.
Publicado: (2024)

Online Edge Coloring is (Nearly) as Easy as Offline
por: Blikstad, Joakim, et al.
Publicado: (2024)

Online Edge Coloring: Sharp Thresholds
por: Blikstad, Joakim, et al.
Publicado: (2025)

Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations
por: Blikstad, Joakim, et al.
Publicado: (2025)

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

Faster Approximate Linear Matroid Intersection
por: Terao, Tatsuya
Publicado: (2026)

Greedy Algorithms for Shortcut Sets and Hopsets
por: Bals, Ben, et al.
Publicado: (2025)

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

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

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

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

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

Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching
por: Zheng, Da Wei, et al.
Publicado: (2023)

Truthful, Credible, and Optimal Auctions for Matroids via Blockchains and Commitments
por: Ganesh, Aadityan, et al.
Publicado: (2025)

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

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

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

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

Matching Composition and Efficient Weight Reduction in Dynamic Matching
por: Bernstein, Aaron, et al.
Publicado: (2024)

Multiplicative Weights Update, Area Convexity and Random Coordinate Descent for Densest Subgraph Problems
por: Nguyen, Ta Duy, et al.
Publicado: (2024)

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

Parallel Batch-Dynamic Algorithms for Spanners, and Extensions
por: Ghaffari, Mohsen, et al.
Publicado: (2025)

Private Interdependent Valuations: New Bounds for Single-Item Auctions and Matroids
por: Eden, Alon, et al.
Publicado: (2024)

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

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

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

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

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

Online Algorithms to Schedule a Proportionate Flexible Flow Shop of Batching Machines
por: Hertrich, Christoph, et al.
Publicado: (2020)

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

Matroid Algorithms Under Size-Sensitive Independence Oracles
por: Banihashem, Kiarash, et al.
Publicado: (2026)

Algorithms for Optimally Shifting Intervals under Intersection Graph Models
por: Honorato-Droguett, Nicolás, et al.
Publicado: (2023)

Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates
por: Mitrović, Slobodan, et al.
Publicado: (2026)

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

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

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