Combinatorial Optimization Reading Group - Benjamin MooreExport this event to calendar

Friday, November 15, 2019 — 1:00 PM EST

Title: A deterministic (1/2 + epsilon)-approximation for submodular maximizztion over a matroid

Speaker: Ben Moore
Affiliation: University of Waterloo
Room: MC 5417

Abstract:

In 1978, it was shown that a natural greedy algorithm gives a 1/2 approximation to submodular maximization subject to a matroid constraint. In 2019, Niv Buchbinder, Moran Feldman, and Mohit Garg gave the first deterministic improvement over the 1/2 approximation, giving a 0.5008-approximation. I will present this result.

Location 
MC - Mathematics & Computer Building
5417
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

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