Online bipartite matching with random arrivals
From MaRDI portal
Publication:5419130
DOI10.1145/1993636.1993716zbMath1288.68288OpenAlexW2079669094MaRDI QIDQ5419130
Publication date: 5 June 2014
Published in: Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1993636.1993716
Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Online algorithms; streaming algorithms (68W27)
Related Items (57)
Approximation algorithms for stochastic combinatorial optimization problems ⋮ Two-sided Online Bipartite Matching and Vertex Cover: Beating the Greedy Algorithm ⋮ Online algorithms with advice for the dual bin packing problem ⋮ Improved analysis of RANKING for online vertex-weighted bipartite matching in the random order model ⋮ Primal Beats Dual on Online Packing LPs in the Random-Order Model ⋮ Online Stochastic Matching: Online Actions Based on Offline Statistics ⋮ A Dynamic Near-Optimal Algorithm for Online Linear Programming ⋮ New results for the \(k\)-secretary problem ⋮ Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order ⋮ Greedy Matching in Bipartite Random Graphs ⋮ Asymptotic analysis for multi-objective sequential stochastic assignment problems ⋮ Bicriteria Online Matching: Maximizing Weight and Cardinality ⋮ Online Matching in Regular Bipartite Graphs ⋮ Ranking on Arbitrary Graphs: Rematch via Continuous Linear Programming ⋮ Near optimal algorithms for online weighted bipartite matching in adversary model ⋮ Primal-dual analysis for online interval scheduling problems ⋮ An Experimental Study of Algorithms for Online Bipartite Matching ⋮ An optimally-competitive algorithm for maximum online perfect bipartite matching with i.i.d. arrivals ⋮ Approximation algorithms for stochastic online matching with reusable resources ⋮ On the advice complexity of online bipartite matching and online stable marriage ⋮ Online stochastic weighted matching algorithm for real‐time shared parking ⋮ Dynamic Relaxations for Online Bipartite Matching ⋮ Secretary and online matching problems with machine learned advice ⋮ Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship ⋮ Near optimal algorithms for online maximum edge-weighted \(b\)-matching and two-sided vertex-weighted \(b\)-matching ⋮ Max-min greedy matching problem: hardness for the adversary and fractional variant ⋮ Markovian online matching algorithms on large bipartite random graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Near-optimal asymmetric binary matrix partitions ⋮ Improved Online Algorithms for Knapsack and GAP in the Random Order Model ⋮ Scheduling In the random-order model ⋮ Best fit bin packing with random order revisited ⋮ On extensions of the deterministic online model for bipartite matching and max-sat ⋮ Online algorithms for maximum cardinality matching with edge arrivals ⋮ Greedy matching: guarantees and limitations ⋮ Online stochastic matching: new algorithms and bounds ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On conceptually simple algorithms for variants of online bipartite matching ⋮ Unnamed Item ⋮ A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games ⋮ Improved online algorithms for Knapsack and GAP in the random order model ⋮ A polyhedral approach to online bipartite matching ⋮ Maximum stable matching with one-sided ties of bounded length ⋮ Online submodular maximization: beating 1/2 made simple ⋮ A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems ⋮ Online Vertex-Weighted Bipartite Matching ⋮ Best Fit Bin Packing with Random Order Revisited ⋮ Stochastic Online Metric Matching ⋮ Monge Properties, Optimal Greedy Policies, and Policy Improvement for the Dynamic Stochastic Transportation Problem ⋮ Online Algorithms for Maximum Cardinality Matching with Edge Arrivals ⋮ Online Stochastic Matching: New Algorithms with Better Bounds ⋮ Budget-Management Strategies in Repeated Auctions ⋮ Learn from history for online bipartite matching ⋮ Unnamed Item ⋮ Oblivious algorithms for the maximum directed cut problem
This page was built for publication: Online bipartite matching with random arrivals
