The Taub Faculty of Computer Science Events and Talks

Contention resolution schemes are an algorithmic technique originally devised in the context of submodular functions maximization. Recent works, however, have extended contention resolution schemes into a robust tool with many applications in various fields such as stochastic optimization, auctions and prophet inequalities. In this talk I will present the concept of contention resolution schemes, and will give a few examples demonstrating some of the power of this technique.

The talk is based on the papers:
- "Submodular function maximization via the multilinear relaxation and contention resolution schemes" by Chandra Chekuri, Jan Vondrák and Rico Zenklusen (SIAM J. Comput, 2014).
- "A stochastic probing problem with applications" by Anupam Gupta and Viswanath Nagarajan (IPCO 2013).
- "Online Contention Resolution Schemes" by Moran Feldman, Ola Svensson and Rico Zenklusen (SODA 2016).