Prophet Matching with General Arrivals
From MaRDI portal
Publication:5085120
DOI10.1287/moor.2021.1152zbMath1492.68146OpenAlexW4200583273MaRDI QIDQ5085120
Tomer Ezra, Michal Feldman, Zhihao Gavin Tang, N. V. Gravin
Publication date: 27 June 2022
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/moor.2021.1152
Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Stopping times; optimal stopping problems; gambling theory (60G40) Online algorithms; streaming algorithms (68W27)
Cites Work
- Unnamed Item
- Comparison of threshold stop rules and maximum for independent nonnegative random variables
- Optimal stopping of independent random variables and maximizing prophets
- Prophet-type inequalities for multi-choice optimal stopping
- Matroid prophet inequalities and applications to multi-dimensional mechanism design
- Online algorithms for maximum cardinality matching with edge arrivals
- An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint
- Maximum matching in the online batch-arrival model
- Stochastic Matching with Commitment
- Bayesian Mechanism Design
- Multi-parameter mechanism design and sequential posted pricing
- Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Nonstochastic Inputs
- Two-sided Online Bipartite Matching and Vertex Cover: Beating the Greedy Algorithm
- Polymatroid Prophet Inequalities
- Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue
- AdWords and generalized online matching
- Comparison of optimal value and constrained maxima expectations for independent random variables
- Semiamarts and finite values
- Online Contention Resolution Schemes
- Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
- Fully Online Matching
- The Two-Sided Game of Googol and Sample-Based Prophet Inequalities
- Beating Greedy for Stochastic Bipartite Matching
- Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model
- Beyond matroids: secretary problem and prophet inequality with general constraints
- Combinatorial Auctions via Posted Prices
- Prophet Inequalities with Limited Information
- Online matching with concave returns
- Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers
- A Unified Continuous Greedy Algorithm for Submodular Maximization
This page was built for publication: Prophet Matching with General Arrivals