Combinatorial Optimization Reading Group - Ian DeHaanExport this event to calendar

Friday, November 25, 2022 — 12:00 PM EST

Title: Greedy algorithm for stochastic matching is a 2-approximatio

Speaker: Ian DeHaan
Affiliation: University of Waterloo
Location: MC 6029 or contact Rian Neogi for Zoom link

Abstract: We will discuss the greedy algorithm for the stochastic matching problem. In this problem, we are given an undirected graph where each edge is assigned a probability p_e in [0, 1] and each vertex is assigned a patience t_v in Z+. We begin each step by probing an edge e which is not adjacent to any edges in our matching. The probe will succeed with probability p_e, and if it does, we add e to our matching. Otherwise, we may not probe e again. We also may not probe edges adjacent to a vertex v more than t_v times. The goal is to maximize the number of edges we add to our matching. A greedy approach was shown to be a 4-approximation for stochastic matching in a previous talk by David Kalichman through analysis of a more general problem. In this talk, we will show that greedy is a 2-approximation for the special case of stochastic matching.

Event tags 

S M T W T F S
27
28
29
30
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
29
30
31
  1. 2022 (146)
    1. December (4)
    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)
  2. 2021 (103)
    1. December (3)
    2. November (7)
    3. October (6)
    4. September (12)
    5. August (6)
    6. July (10)
    7. June (12)
    8. May (7)
    9. April (9)
    10. March (13)
    11. February (8)
    12. January (10)
  3. 2020 (119)
  4. 2019 (167)
  5. 2018 (136)
  6. 2017 (103)
  7. 2016 (137)
  8. 2015 (136)
  9. 2014 (88)
  10. 2013 (48)
  11. 2012 (39)
  12. 2011 (36)
  13. 2010 (40)
  14. 2009 (40)
  15. 2008 (39)
  16. 2007 (15)