On conceptually simple algorithms for variants of online bipartite matching
DOI10.1007/978-3-319-89441-6_19zbMath1436.91085arXiv1706.09966OpenAlexW2728346207MaRDI QIDQ5915658
Denis Pankratov, Amirali Salehi-Abari, Allan Borodin
Publication date: 22 June 2018
Published in: Theory of Computing Systems, Approximation and Online Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1706.09966
online algorithmsbipartite matchinggreedy algorithmsonline bipartite matchingpriority algorithmspriority modeladversarial modelcategory-advice algorithmmin greedy algorithmonline IID modelconceptually simple algorithms
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Randomized algorithms (68W20) Matching models (91B68) Online algorithms; streaming algorithms (68W27)
Related Items (6)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Greedy matching: guarantees and limitations
- On sum coloring and sum multi-coloring for restricted families of graphs
- Models of greedy algorithms for graph problems
- Randomized priority algorithms
- Priority algorithms for the subset-sum problem
- The advice complexity of a class of hard online problems
- Erratum to: ``Greedy matching: guarantees and limitations
- (Incremental) priority algorithms
- Online independent sets.
- Differential equations for random processes and random graphs
- On the advice complexity of the \(k\)-server problem
- Graph sketching and streaming: new approaches for analyzing massive graphs
- Bipartite matching in the semi-streaming model
- On graph problems in a semi-streaming model
- Greedy Local Improvement and Weighted Set Packing Approximation
- Bayesian Mechanism Design
- Online Stochastic Matching: Online Actions Based on Offline Statistics
- Improved Bounds for Online Preemptive Matching
- Bounds on Greedy Algorithms for MAX SAT
- Online Stochastic Weighted Matching: Improved Approximation Algorithms
- Maximum Matching in Semi-streaming with Few Passes
- Linear-Time Approximation for Maximum Weight Matching
- Improved Approximation Guarantees for Weighted Matching in the Semi-streaming Model
- Improved Bounds for Online Stochastic Matching
- Randomized greedy matching. II
- Deterministic Algorithms for Submodular Maximization Problems
- Randomization Can Be as Helpful as a Glimpse of the Future in Online Computation
- Online Stochastic Matching: Beating 1-1/e
- Online Stochastic Matching: New Algorithms with Better Bounds
- Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
- 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
- Solutions of ordinary differential equations as limits of pure jump markov processes
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Approximation and Online Algorithms
- Randomized Primal-Dual Analysis of RANKING for Online Bipartite Matching
- Better bounds for matchings in the streaming model
- An Experimental Study of Algorithms for Online Bipartite Matching
This page was built for publication: On conceptually simple algorithms for variants of online bipartite matching
