Friday, October 11, 2019

Friday, October 11, 2019 — 1:00 PM EDT

Title: Maximizing a Monotone Submodular Function subject to a Matroid Constraint

Speaker: Justin Toth Affiliation: University of Waterloo Room: MC 5417

Abstract:

Based on the paper by Calinescu, Chekuri, Pál, and Vondrák of the same title. We will study a randomized $(1-\frac{1}{e})$-approximation algorithm for the titular problem. 

Friday, October 11, 2019 — 3:30 PM EDT

Title: On the depth of cutting planesOn the depth of cutting planes

Speaker: Laurent Poirrier Affiliation: University of Waterloo Room: MC 5501

Abstract:

We tackle one of the most important open problems in computational integer programming: cut selection.

For four decades, cutting planes were believed to be useful only for structured combinatorial problems. This changed in 1995 when Balas, Ceria and Cornuéjols showed that Gomory cuts could helpfully strengthen the formulation of general integer programming problems. Since then, many other cut generation techniques have been developed, but their practical success has been moderate at best.

S M T W T F S
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
2
  1. 2019 (159)
    1. November (12)
    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)