Greedy matching: guarantees and limitations
From MaRDI portal
Publication:513303
DOI10.1007/s00453-015-0062-2zbMath1359.68289arXiv1505.04198OpenAlexW2146319320MaRDI QIDQ513303
Bert Besser, Matthias Poloczek
Publication date: 6 March 2017
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1505.04198
Related Items
Greedy Matching in Bipartite Random Graphs, Unnamed Item, Advice complexity of adaptive priority algorithms, Erratum to: ``Greedy matching: guarantees and limitations, On extensions of the deterministic online model for bipartite matching and max-sat, Greedy Bipartite Matching in Random Type Poisson Arrival Model, On conceptually simple algorithms for variants of online bipartite matching, Advice complexity of priority algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On linear and semidefinite programming relaxations for hypergraph matching
- On sum coloring and sum multi-coloring for restricted families of graphs
- Pairwise kidney exchange
- Models of greedy algorithms for graph problems
- Randomized priority algorithms
- Priority algorithms for graph optimization problems
- Matching theory
- An algebraic matching algorithm
- (Incremental) priority algorithms
- Maximum skew-symmetric flows and matchings
- On the complexity of approximating \(k\)-set packing
- Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization
- Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems
- Bounds on Greedy Algorithms for MAX SAT
- On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
- Algebraic Algorithms for Matching and Matroid Problems
- Randomized greedy matching
- An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
- An Analysis of the Greedy Heuristic for Independence Systems
- Randomized greedy matching. II
- Analysis of a Simple Greedy Matching Algorithm on Random Cubic Graphs
- A natural barrier in random greedy hypergraph matching
- Paths, Trees, and Flowers
- Ranking on Arbitrary Graphs: Rematch via Continuous LP with Monotone and Boundary Condition Constraints
- Online bipartite matching with unknown distributions
- Online bipartite matching with random arrivals
- Power balance and apportionment algorithms for the United States Congress
- Algorithms – ESA 2004
- Transversals and matroid partition
- Concentration of Measure for the Analysis of Randomized Algorithms
