University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Combinatorial Optimization Reading Group - Zishen QuExport this event to calendar

Friday, November 1, 2019 — 1:00 PM EDT

Title: Maximizing non-monotone submodular functions

Speaker: Zishen Qu
Affiliation: University of Waterloo
Room: MC 5417

Abstract:

Optimization of non-monotone submodular functions has applications in the maximum cut and maximum directed cut problems for graphs. Despite the lack of structure, we can derive rather strong results on problems of this type. We will prove that there is a deterministic algorithm producing a (1/3)-approximation for this problem. Using the value oracle model, we also have the hardness result that there can be no polynomial time (1/2+ε)-approximation. The results presented here were produced in Feige, Mirrokni, and Vondrák (2007). 

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

Waterloo, ON N2L 3G1
Canada

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