Online Contention Resolution Schemes with Applications to Bayesian Selection Problems
From MaRDI portal
Publication:5856151
DOI10.1137/18M1226130OpenAlexW3133734588MaRDI QIDQ5856151
Rico Zenklusen, Moran Feldman, Ola Svensson
Publication date: 24 March 2021
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/18m1226130
online algorithmsmatroidsprophet inequalitiesstochastic probingcontention resolution schemesoblivious posted pricing
Analysis of algorithms (68W40) Combinatorics in computer science (68R05) Online algorithms; streaming algorithms (68W27)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- When LP is the cure for your matching woes: improved bounds for stochastic matchings
- Combinatorial auctions with decreasing marginal utilities
- Matroid Secretary Problem in the Random-Assignment Model
- Multi-parameter mechanism design and sequential posted pricing
- Submodular secretary problem and extensions
- Maximizing Non-monotone Submodular Functions
- Submodular Stochastic Probing on Matroids
- Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
- Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Nonstochastic Inputs
- Optimal Auction Design
- The Submodular Secretary Problem Goes Linear
- A Stochastic Probing Problem with Applications
- An Optimal Algorithm for Monte Carlo Estimation
- Constrained Submodular Maximization via a Nonsymmetric Technique
- Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
- A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem
- Submodular Maximization with Cardinality Constraints
- Matroid prophet inequalities
- Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
- Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers
- A Unified Continuous Greedy Algorithm for Submodular Maximization
This page was built for publication: Online Contention Resolution Schemes with Applications to Bayesian Selection Problems