Online bipartite matching with unknown distributions
From MaRDI portal
Publication:5419129
DOI10.1145/1993636.1993715zbMath1288.68287OpenAlexW2104224720MaRDI QIDQ5419129
Pushkar Tripathi, Aranyak Mehta, C. Karande
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.1993715
Combinatorics in computer science (68R05) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Online algorithms; streaming algorithms (68W27)
Related Items
Approximation algorithms for stochastic combinatorial optimization problems, Two-sided Online Bipartite Matching and Vertex Cover: Beating the Greedy Algorithm, Secretary Markets with Local Information, 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, A stochastic algorithm for online bipartite resource allocation problems, Online Stochastic Matching: Online Actions Based on Offline Statistics, A Dynamic Near-Optimal Algorithm for Online Linear Programming, Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order, Greedy Matching in Bipartite Random Graphs, Bicriteria Online Matching: Maximizing Weight and Cardinality, Ranking on Arbitrary Graphs: Rematch via Continuous Linear Programming, Near optimal algorithms for online weighted bipartite matching in adversary model, 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, Online allocation and display ads optimization with surplus supply, 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, Unnamed Item, Unnamed Item, Scheduling In the random-order model, 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, Unnamed Item, Unnamed Item, On conceptually simple algorithms for variants of online bipartite matching, Online submodular maximization: beating 1/2 made simple, Online Vertex-Weighted Bipartite Matching, Stochastic Online Metric Matching, 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
