Online stochastic weighted matching: improved approximation algorithms

DOI10.1007/978-3-642-25510-6_15MaRDI QIDQ3102585zbMATH OpenOpenAlexFDO

Authors Bernhard Haeupler, Morteza Zadimoghaddam, Vahab S. Mirrokni

Publication date 5 December 2011

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-25510-6_15

zbMATH Keywords

ad allocationapproximation algorithmcompetitive analysisonline stochastic matching

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Internet topics (68M11) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27) Marketing, advertising (90B60)

Recommendations

• Online stochastic matching: new algorithms with better bounds
• Online stochastic matching: new algorithms and bounds
• Improved Bounds for Online Stochastic Matching

Cited in

(33)

• Near optimal algorithms for online weighted bipartite matching in adversary model
• A polyhedral approach to online bipartite matching
• Online stochastic matching: new algorithms and bounds
• Learn from history for online bipartite matching
• Online total bipartite matching problem
• An optimally-competitive algorithm for maximum online perfect bipartite matching with i.i.d. arrivals
• Attenuate locally, win globally: attenuation-based frameworks for online stochastic matching with timeouts
• Advice complexity of online non-crossing matching
• Online matching and ad allocation
• Bicriteria online matching: maximizing weight and cardinality
• A Polyhedral Approach to Online Bipartite Matching
• Improved Bounds for Online Stochastic Matching
• Online submodular welfare maximization: greedy beats 1/2 in random order
• Online Weighted Matching
• Online vertex-weighted bipartite matching. Beating \(1-\frac{1}{e}\) with random arrivals
• scientific article; zbMATH DE number 7376006 (Why is no real title available?)
• Greedy bipartite matching in random type Poisson arrival model
• Technical note -- Assortment planning for two-sided sequential matching markets
• Dynamic Relaxations for Online Bipartite Matching
• Algorithms for Online Matching, Assortment, and Pricing with Tight Weight-Dependent Competitive Ratios
• Stochastic Matching with Few Queries: New Algorithms and Tools
• Online stochastic matching: new algorithms with better bounds
• scientific article; zbMATH DE number 7053386 (Why is no real title available?)
• Approximation algorithms for stochastic online matching with reusable resources
• Online 2-stage stable matching
• Online stochastic weighted matching algorithm for real‐time shared parking
• The power of multiple choices in online stochastic matching
• Edge-weighted online bipartite matching
• Adwords in a panorama
• Improved competitive ratio for edge-weighted online stochastic matching
• Two-sided capacitated submodular maximization in gig platforms
• Online matching meets sampling without replacement
• Near optimal algorithms for online maximum edge-weighted b-matching and two-sided vertex-weighted b-matching

This page was built for publication: Online stochastic weighted matching: improved approximation algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3102585)