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 - Kanstantsin PashkovichExport this event to calendar

Friday, July 5, 2019 — 1:00 PM EDT

Title: Quasi-popular Matchings, Optimality, and Extended Formulations

Speaker: Kanstantsin Pashkovich
Affiliation: University of Waterloo
Room: MC 5479

Abstract:

The goal of this talk is to obtain efficient algorithms for computing desirable matchings (wrt cost) by paying the price of mildly relaxing popularity. The main positive result in the talk is a bi-criteria algorithm that finds in polynomial time a "quasi-popular" matching of cost at most opt, where opt is the cost of a min-cost popular matching. Key to the algorithm are a number of results for certain polytopes related to matchings and that we believe to be of independent interest. In particular, we present a polynomial-size extended formulation for an integral polytope sandwiched between the popular and "quasi-popular" matching polytopes. 

Based on paper "Quasi-popular Matchings, Optimality, and Extended Formulations” by Yuri Faenza and Telikepalli Kavitha.

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

Waterloo, ON N2L 3G1
Canada

S M T W T F S
26
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
31
1
2
3
4
5
  1. 2020 (75)
    1. August (8)
    2. July (17)
    3. June (11)
    4. May (6)
    5. March (11)
    6. February (11)
    7. 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)