About

Much of the progress in solving discrete optimization problems, especially in terms of approximation algorithms, has come from designing novel continuous relaxations. The primary tools in this area are linear programming and semidefinite programming. Other forms of relaxations have also been developed, such as multilinear relaxation for submodular optimization. In this workshop, we explore the state-of-the-art techniques for performing discrete optimization based on continuous relaxations of the underlying problem, as well as our current understanding of the limitations of this kind of approach. We focus on LP/SDP relaxations and techniques for rounding their solutions, as well as methods for submodular optimization, both in the offline and online setting. We also investigate the limits of such relaxations and hardness of approximation results.

All presentations take place at the Calvin Lab auditorium.

Chairs/Organizers
Seffi Naor (Technion Israel Institute of Technology)
Invited Participants

Anna Adamaszek (University of Copenhagen), Nima Anari Ahmadipouranari (Stanford University), Farid Alizadeh (Rutgers University), Jason Altschuler (MIT), Kyriakos Axiotis (MIT), Nikhil Bansal (Eindhoven University of Technology), Charles Carlson (University of Illinois Urbana-Champaign), Deeparnab Chakrabarty (Dartmouth College), Parinya Chalermsook (Aalto University), Moses Charikar (Stanford University), Chandra Chekuri (University of Illinois Urbana-Champaign), Ken Clarkson (IBM Almaden), Michael Cohen (MIT), Daniel Dadush (Centrium Wiskunde & Informatica), Damek Davis (Cornell University), Nikhil R. Devanur (Microsoft Research), Jelena Diakonikolas (Boston University), Reza Eghbali (University of Washington), Friedrich Eisenbrand (École Polytechnique Fédérale de Lausann), Alina Ene (Boston University), Maryam Fazel (University of Washington), Uri Feige (Weizmann Institute of Science), Sam Fiorini (Université Libre de Bruxelles), Shashwat Garg (TU Eindhoven), Michel Goemans (MIT), Fabrizio Grandoni (IDSIA, University of Lugano), Ben Grimmer (Cornell University), Krystal Guo (Université Libre de Bruxelles), Anupam Gupta (Carnegie Mellon University), Swati Gupta (MIT), Nick Harvey (University of British Columbia), Robert Hildebrand (IBM T.J. Watson Research Center), Rebecca Hoberg (University of Washington), Fatma Kılınç-Karzan (Carnegie Mellon University), Ravindran Kannan (Microsoft Research India), Sanjeev Khanna (University of Pennsylvania), Matthias Koppe (UC Davis), Rasmus Kyng (Yale University), Bundit Laekhanukit (Weizmann Institute of Science), Lap-Chi Lau (University of Waterloo), Euiwoong Lee (Carnegie Mellon University), Jon Lee (University of Michigan), Shi Li (SUNY Buffalo), Chris Liaw (University of British Columbia), Cong Han Lim (University of Wisconsin-Madison), Mike Luby (Qualcomm), Shiqian Ma (University of California, Davis), Konstantin Makarychev (Northwestern University), Alex Makelov (MIT), Aryan Mokhtari (University of Pennsylvania), Sarah Maria Morell (EPFL), Walaa Moursi (University of British Columbia), Seffi Naor (Technion – Israel Institute of Technology), Huy Nguyen (Northeastern University), Sasho Nikolov (University of Toronto), Debmalya Panigrahi (Duke University), Pablo Parrilo (MIT), Kostya Pashkovich (University of Waterloo), Sebastian Pokutta (Georgia Institute of Technology), Yuval Rabani (Hebrew University of Jerusalem), Prasad Raghavendra (UC Berkeley), R Ravi (Carnegie Mellon University), Jim Renegar (Cornell University), Alireza Rezaei (University of Washington), Thomas Rothvoß (University of Washington), Amin Saberi (Stanford University), Piotr Sankowski (University of Warsaw), Andreas Schmid (Max-Planck-Institut für Informatik), Ludwig Schmidt (MIT), Tselil Schramm (UC Berkeley), Roy Schwartz (Technion - Israel Institute of Technology), David Shmoys (Cornell University), Aaron Sidford (Stanford University), Mohit Singh (Georgia Institute of Technology), Sahil Singla (Carnegie Mellon University), Chaitanya Swamy (University of Waterloo),  Prasad Tetali (Georgia Institue of Technology), Dimitris Tsipras (MIT), Levent Tunçel (University of Waterloo), Lieven Vandenberghe (UCLA), László Végh (London School of Economics), Soledad Villar (University of Texas at Austin), Cynthia Vinzant (North Carolina State University), Adrian Vladu (Boston University), Jan Vondrák (Stanford University), David Wajc (Carnegie Mellon University), Karol Węgrzycki (Unversity of Warsaw), David Williamson (Cornell University), Steve Wright (University of Wisconsin-Madison), Chenyang Yuan (MIT), Rico Zenklusen (ETH Zürich).