Online Contention Resolution Schemes

DOI10.1137/1.9781611974331.CH72zbMATH Open1411.68203arXiv1508.00142OpenAlexW2953135426MaRDI QIDQ4575652FDOQ4575652

Moran Feldman, Rico Zenklusen, Ola Svensson

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: We introduce a new rounding technique designed for online optimization problems, which is related to contention resolution schemes, a technique initially introduced in the context of submodular function maximization. Our rounding technique, which we call online contention resolution schemes (OCRSs), is applicable to many online selection problems, including Bayesian online selection, oblivious posted pricing mechanisms, and stochastic probing models. It allows for handling a wide set of constraints, and shares many strong properties of offline contention resolution schemes. In particular, OCRSs for different constraint families can be combined to obtain an OCRS for their intersection. Moreover, we can approximately maximize submodular functions in the online settings we consider. We, thus, get a broadly applicable framework for several online selection problems, which improves on previous approaches in terms of the types of constraints that can be handled, the objective functions that can be dealt with, and the assumptions on the strength of the adversary. Furthermore, we resolve two open problems from the literature; namely, we present the first constant-factor constrained oblivious posted price mechanism for matroid constraints, and the first constant-factor algorithm for weighted stochastic probing with deadlines.

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

zbMATH Keywords

online algorithmsmatroidsprophet inequalitiesstochastic probingcontention resolution schemesoblivious posted pricing

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Stochastic programming (90C15)

Cited In (22)

• Prophet Matching with General Arrivals
• Optimal prophet inequality with less than one sample
• Prophet secretary for \(k\)-knapsack and \(l\)-matroid intersection via continuous exchange property
• An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint
• Improved prophet inequalities for combinatorial welfare maximization with (approximately) subadditive agents
• Approximation algorithms for stochastic combinatorial optimization problems
• An $O(\log \log m)$ Prophet Inequality for Subadditive Combinatorial Auctions
• Prophet Inequalities for Independent and Identically Distributed Random Variables from an Unknown Distribution
• Buy-many mechanisms for many unit-demand buyers
• Optimal item pricing in online combinatorial auctions
• Formal barriers to simple algorithms for the matroid secretary problem
• Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Nonstochastic Inputs
• Submodular Maximization with Uncertain Knapsack Capacity
• Optimal item pricing in online combinatorial auctions
• Guess free maximization of submodular and linear sums
• Title not available (Why is that?)
• Prophet inequalities vs. approximating optimum online
• Towards an optimal contention resolution scheme for matchings
• A simple optimal contention resolution scheme for uniform matroids
• Contention resolution, matrix scaling and fair allocation
• Title not available (Why is that?)
• Posted Price Mechanisms and Optimal Threshold Strategies for Random Arrivals

This page was built for publication: Online Contention Resolution Schemes

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