Combinatorial Optimization Reading Group - David KalichmanExport this event to calendar

Friday, September 30, 2022 — 12:00 PM EDT

Title: Stochastic Probing with Applications

Speaker: David Kalichman
Affiliation: University of Waterloo
Location: MC 6029 or contact Rian Neogi for the Zoom link

Abstract: We will explore a stochastic probing problem. Given a set of elements which have weights and independent probabilities of being "active," the goal is to construct a subset of active elements of maximum weight. To form such a set, we must "probe" elements sequentially to determine whether they are active. If a probed element turns out to be active, then we must include it in our set. In addition, two packing constraints must be satisfied - one for the set of active elements, and another for the set of probed elements. In this talk, I will present a performance guarantee for the greedy algorithm in the unweighted case and an algorithm for the weighted case that uses contention resolution schemes. Finally, I will discuss applications of these algorithms to pricing items in Bayesian auctions and to online dating and kidney exchange problems.

S M T W T F S
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
1
2
3
4
  1. 2023 (13)
    1. February (5)
    2. January (8)
  2. 2022 (150)
    1. December (8)
    2. November (18)
    3. October (15)
    4. September (11)
    5. August (2)
    6. July (17)
    7. June (17)
    8. May (10)
    9. April (12)
    10. March (18)
    11. February (10)
    12. January (13)
  3. 2021 (103)
  4. 2020 (119)
  5. 2019 (167)
  6. 2018 (136)
  7. 2017 (103)
  8. 2016 (137)
  9. 2015 (136)
  10. 2014 (88)
  11. 2013 (48)
  12. 2012 (39)
  13. 2011 (36)
  14. 2010 (40)
  15. 2009 (40)
  16. 2008 (39)
  17. 2007 (15)