Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Contention Resolution Schemes: Offline and Online
event speaker icon
Moran Feldman (Open University)
event date icon
Wednesday, 15.06.2016, 12:30
event location icon
Taub 201
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).