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.

SAGT 2020 Best Paper Award

Friday, July 17, 2020

Jochen Koenemann, Kanstantsin Pashkovich and Natig Tofigzade were announced the recipients of the SAGT 2020 Best Paper Award for their paper "Approximating Stable Matchings with Ties of Bounded Size".

The abstract of the paper reads: "Finding a stable matching is one of the central problems in algorithmic game theory. If participants are allowed to have ties and incomplete preferences, computing a stable matching of maximum cardinality is known to be NP-hard. In this paper we present a (3L−2)/(2L−1)-approximation algorithm for the stable matching problem with ties of size at most L and incomplete lists. Our result matches the known lower bound on the integrality gap for the associated LP formulation."

The results in the paper form the basis for Natig's recently completed Master's thesis entitled "An Algorithm for Stable Matching with Approximation up to the Integrality Gap".

SAGT 202SAGT 2020 is the 13th Symposium on Algorithmic Game Theory. The purpose of SAGT is to bring together researchers from Computer Science, Economics, Mathematics, Operations Research, Psychology, Physics, and Biology to present and discuss original research at the intersection of Algorithms and Game Theory.

  1. 2020 (9)
    1. July (2)
    2. June (5)
    3. April (2)
  2. 2019 (30)
    1. December (1)
    2. November (2)
    3. October (3)
    4. September (3)
    5. July (2)
    6. June (6)
    7. May (3)
    8. April (4)
    9. March (3)
    10. January (3)
  3. 2018 (21)
    1. October (3)
    2. August (2)
    3. July (3)
    4. June (2)
    5. May (2)
    6. April (3)
    7. March (1)
    8. February (1)
    9. January (4)
  4. 2017 (16)
  5. 2016 (22)
  6. 2015 (26)
  7. 2014 (25)
  8. 2013 (13)
  9. 2012 (12)
  10. 2011 (9)
  11. 2010 (5)
  12. 2009 (5)
  13. 2008 (2)
  14. 2007 (1)
  15. 2006 (4)
  16. 2005 (6)
  17. 2003 (1)
  18. 2002 (2)
  19. 2001 (2)