Online stochastic matching: new algorithms and bounds

DOI10.1007/S00453-020-00698-3MaRDI QIDQ2006938zbMATH OpenOpenAlexFDO

Authors Brian Brubach, Karthik Abinav Sankararaman, Aravind Srinivasan, Pan Xu

Publication date 12 October 2020

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.06395

zbMATH Keywords

bipartite matchingInternet advertisingonline algorithmsrandomized algorithms

Mathematics Subject Classification ID

Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27) Marketing, advertising (90B60) Stochastic programming (90C15) Combinatorial optimization (90C27) Matching models (91B68)

Abstract: Online matching has received significant attention over the last 15 years due to its close connection to Internet advertising. As the seminal work of Karp, Vazirani, and Vazirani has an optimal (1 - 1/e) competitive ratio in the standard adversarial online model, much effort has gone into developing useful online models that incorporate some stochasticity in the arrival process. One such popular model is the "known I.I.D. model" where different customer-types arrive online from a known distribution. We develop algorithms with improved competitive ratios for some basic variants of this model with integral arrival rates, including (a) the case of general weighted edges, where we improve the best-known ratio of 0.667 due to Haeupler, Mirrokni and Zadimoghaddam to 0.705; and (b) the vertex-weighted case, where we improve the 0.7250 ratio of Jaillet and Lu to 0.7299. We also consider an extension of stochastic rewards, a variant where each edge has an independent probability of being present. For the setting of stochastic rewards with non-integral arrival rates, we present a simple optimal non-adaptive algorithm with a ratio of 1 - 1/e. For the special case where each edge is unweighted and has a uniform constant probability of being present, we improve upon 1 - 1/e by proposing a strengthened LP benchmark.

Recommendations

• New algorithms, better bounds, and a novel model for online stochastic matching
• Online stochastic matching: new algorithms with better bounds
• Online stochastic weighted matching: improved approximation algorithms
• Improved Bounds for Online Stochastic Matching

Cites work

• Algorithms for Secretary Problems on Graphs and Hypergraphs
• An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions
• Attenuate locally, win globally: attenuation-based frameworks for online stochastic matching with timeouts
• Dependent rounding and its applications to approximation algorithms
• Near optimal online algorithms and fast approximation algorithms for resource allocation problems
• Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs
• Online matching and ad allocation
• Online stochastic matching with unequal probabilities
• Online Stochastic Matching: Beating 1-1/e
• Online stochastic matching: new algorithms with better bounds
• Online stochastic weighted matching: improved approximation algorithms
• Online vertex-weighted bipartite matching and single-bid budgeted allocations
• The online stochastic generalized assignment problem

Cited in

(26)

• A polyhedral approach to online bipartite matching
• Attenuate locally, win globally: attenuation-based frameworks for online stochastic matching with timeouts
• Improved online algorithms for jumbled matching
• Online minimum matching with uniform metric and random arrivals
• The Power of Rejection in Online Bottleneck Matching
• Online stochastic weighted matching: improved approximation algorithms
• Improved Bounds for Online Stochastic Matching
• New algorithms, better bounds, and a novel model for online stochastic matching
• scientific article; zbMATH DE number 6850371 (Why is no real title available?)
• Prophet matching with general arrivals
• Dynamic Relaxations for Online Bipartite Matching
• Online primal dual meets online matching with stochastic rewards: configuration LP to the rescue
• Stochastic Matching with Few Queries: New Algorithms and Tools
• Online stochastic matching: new algorithms with better bounds
• Online stochastic matching with unequal probabilities
• Online matching with concave returns
• Approximation and Online Algorithms
• Approximation algorithms for stochastic online matching with reusable resources
• Online 2-stage stable matching
• scientific article; zbMATH DE number 7740914 (Why is no real title available?)
• The power of multiple choices in online stochastic matching
• Online Matching with Stochastic Rewards: Optimal Competitive Ratio via Path-Based Formulation
• Online primal dual meets online matching with stochastic rewards: configuration LP to the rescue
• Improved competitive ratio for edge-weighted online stochastic matching
• Two-sided capacitated submodular maximization in gig platforms
• Special issue: Selected papers based on the presentations at the workshop ``Match-UP: Matching under preferences -- algorithms and complexity, Reykjavík, Iceand, July 2008

This page was built for publication: Online stochastic matching: new algorithms and bounds

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