Cover Image

Greedy matroid base packings with applications to dynamic graph density and orientations

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Arkhipov, Pavel, Kolmogorov, Vladimir
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

Faster algorithms for packing forests in graphs and related problems
by: Arkhipov, Pavel, et al.
Published: (2024)

Blossom VI: A Practical Minimum Weight Perfect Matching Algorithm
by: Arkhipov, Pavel, et al.
Published: (2026)

Bounded indegree $k$-forests problem and a faster algorithm for directed graph augmentation
by: Arkhipov, Pavel, et al.
Published: (2024)

Tighter relaxations for MAP-MRF optimization via Singleton Arc Consistency
by: Lev-Ran, Asaf, et al.
Published: (2026)

A computational study of Gomory-Hu construction tree algorithms
by: Kolmogorov, Vladimir
Published: (2022)

A simpler and parallelizable $O(\sqrt{\log n})$-approximation algorithm for Sparsest Cut
by: Kolmogorov, Vladimir
Published: (2023)

OrderedCuts: A new approach for computing Gomory-Hu tree
by: Kolmogorov, Vladimir
Published: (2022)

A Fast Approximation Algorithm for the Minimum Balanced Vertex Separator in a Graph
by: Kolmogorov, Vladimir, et al.
Published: (2026)

Simple parallel estimation of the partition ratio for Gibbs distributions
by: Harris, David G., et al.
Published: (2025)

FPT algorithms over linear delta-matroids with applications
by: Eiben, Eduard, et al.
Published: (2025)

A new notion of commutativity for the algorithmic Lovász Local Lemma
by: Harris, David G., et al.
Published: (2020)

$k$-times bin packing and its application to fair electricity distribution
by: Baghel, Dinesh Kumar, et al.
Published: (2023)

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

On Bounds for Greedy Schemes in String Optimization based on Greedy Curvatures
by: Li, Bowen, et al.
Published: (2024)

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

Near-Optimal Parallel Approximate Counting via Sampling
by: Harris, David G., et al.
Published: (2026)

Representative set statements for delta-matroids and the Mader delta-matroid
by: Wahlström, Magnus
Published: (2023)

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

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

Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
by: Bonamy, Marthe, et al.
Published: (2022)

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)

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

Parameter estimation for Gibbs distributions
by: Harris, David G., et al.
Published: (2020)

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

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

The Power of Greedy for Online Minimum Cost Matching on the Line
by: Balkanski, Eric, et al.
Published: (2022)

A Threshold Greedy Algorithm for Noisy Submodular Maximization
by: Chen, Wenjing, et al.
Published: (2023)

Simple Construction of Greedy Trees and Greedy Permutations
by: Chubet, Oliver, et al.
Published: (2024)

Maximum Coverage $k$-Antichains and Chains: A Greedy Approach
by: Cáceres, Manuel, et al.
Published: (2025)

Discrete Effort Distribution via Regret-enabled Greedy Algorithm
by: Cao, Song, et al.
Published: (2025)

Greedy Conjecture for the Shortest Common Superstring Problem and its Strengthenings
by: Nikolaev, Maksim
Published: (2024)

A Unified Framework for Analysis of Randomized Greedy Matching Algorithms
by: Derakhshan, Mahsa, et al.
Published: (2026)

A Simple Average-case Analysis of Recursive Randomized Greedy MIS
by: Dalirrooyfard, Mina, et al.
Published: (2026)

Interdiction of minimum spanning trees and other matroid bases
by: Weninger, Noah, et al.
Published: (2024)

Expected Cost of Greedy Online Facility Assignment on Regular Polygons (v3)
by: Riad, Md. Rawha Siddiqi, et al.
Published: (2025)

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

On 2-strong connectivity orientations of mixed graphs and related problems
by: Georgiadis, Loukas, et al.
Published: (2023)

Predict, Reposition, and Allocate: A Greedy and Flow-Based Architecture for Sustainable Urban Food Delivery
by: Makhdomi, Aqsa Ashraf, et al.
Published: (2025)