Online Contention Resolution Schemes with Applications to Bayesian Selection Problems

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

zbMATH Keywords

online algorithmsmatroidsprophet inequalitiesstochastic probingcontention resolution schemesoblivious posted pricing

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorics in computer science (68R05) Online algorithms; streaming algorithms (68W27)

Related Items (1)

A Framework for the Secretary Problem on the Intersection of Matroids

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