Online Contention Resolution Schemes

DOI10.1137/1.9781611974331.ch72zbMath1411.68203arXiv1508.00142OpenAlexW2953135426MaRDI QIDQ4575652

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)

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

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

Related Items (20)

Approximation algorithms for stochastic combinatorial optimization problems ⋮ Formal barriers to simple algorithms for the matroid secretary problem ⋮ Optimal item pricing in online combinatorial auctions ⋮ Prophet Matching with General Arrivals ⋮ Prophet Inequalities for Independent and Identically Distributed Random Variables from an Unknown Distribution ⋮ Prophet inequalities vs. approximating optimum online ⋮ Towards an optimal contention resolution scheme for matchings ⋮ Optimal prophet inequality with less than one sample ⋮ Unnamed Item ⋮ A simple optimal contention resolution scheme for uniform matroids ⋮ Unnamed Item ⋮ Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Nonstochastic Inputs ⋮ Improved prophet inequalities for combinatorial welfare maximization with (approximately) subadditive agents ⋮ Guess free maximization of submodular and linear sums ⋮ Submodular Maximization with Uncertain Knapsack Capacity ⋮ Contention resolution, matrix scaling and fair allocation ⋮ An $O(\log \log m)$ Prophet Inequality for Subadditive Combinatorial Auctions ⋮ Posted Price Mechanisms and Optimal Threshold Strategies for Random Arrivals ⋮ 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

This page was built for publication: Online Contention Resolution Schemes