Workshops
Fall 2017

Discrete Optimization via Continuous Relaxation

Sep. 11Sep. 15, 2017

Add to Calendar

Organizers:

Chandra Chekuri (University of Illinois, Urbana-Champaign; chair), Nikhil Bansal (Technische Universiteit Eindhoven), Seffi Naor (Technion Israel Institute of Technology), Mohit Singh (Georgia Institute of Technology)

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.

Enquiries may be sent to the organizers workshop_opt1 [at] lists [dot] simons [dot] berkeley [dot] edu (at this address).

All presentations take place at the Melvin Calvin Auditorium.

Invited Participants: 

Anna Adamaszek (University of Copenhagen), Nima Anari Ahmadipouranari (Stanford University), Farid Alizadeh (Rutgers University), Jason Altschuler (MIT), Kyriakos Axiotis (MIT), Afonso Bandeira (Courant Institute of Mathematical Sciences, NYU), Manuel Blum (Carnegie Mellon University), Lenore Blum (Carnegie Mellon University), Deeparnab Chakrabarty (Dartmouth College), Parinya Chalermsook (Aalto University), Moses Charikar (Stanford University), 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), Leonid Gurvits (City University of New York), Moritz Hardt (UC Berkeley), Nick Harvey (University of British Columbia), Robert Hildebrand (IBM T.J. Watson Research Center), Rebecca Hoberg (University of Washington), Dorit Hochbaum (UC Berkeley), Stefanie Jegelka (MIT), Ravi Kannan (Microsoft Research India), Sanjeev Khanna (University of Pennsylvania), Fatma Kılınç-Karzan (Carnegie Mellon University), Alexandra Kolla (University of Illinois at Urbana-Champaign), Matthias Köppe (University of California, Davis), Robi Krauthgamer (Weizmann Institute of Science), 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), Aleksander Mądry (MIT), Konstantin Makarychev (Northwestern University), Alex Makelov (MIT), Raghu Meka (UCLA), Jarrod Millman (UC Berkeley), Aryan Mokhtari (University of Pennsylvania), Sarah Maria Morell (EPFL), Walaa Moursi (University of British Columbia), Seffi Naor (Technion – Israel Institute of Technology), Rad Niazadeh (Stanford University), Sasho Nikolov (University of Toronto), Shayan Oveis Gharan (University of Washington), 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), Ben Recht (UC Berkeley), 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, Ludwig Schmidt (MIT), Tselil Schramm (UC Berkeley), Roy Schwartz (Technion - Israel Institute of Technology), Jonah Sherman (UC Berkeley), David Shmoys (Cornell University), Aaron Sidford (Stanford University), Sahil Singla (Carnegie Mellon University), Aravind Srinivasan (University of Maryland), Nikhil Srivastava (UC Berkeley), 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), Nisheeth Kumar Vishnoi (École Polytechnique Fédérale de Lausanne), Adrian Vladu (Boston University), Jan Vondrák (Stanford University), David Wajc (Carnegie Mellon University), Di Wang (UC Berkeley), Mengdi Wang (Princeton University), Karol Węgrzycki (Unversity of Warsaw), David Williamson (Cornell University), Steve Wright (University of Wisconsin-Madison), Lin Yang (Princeton University), Sheng Yang (University of Maryland), Yinyu Ye (Stanford University), Chenyang Yuan (MIT), Rico Zenklusen (ETH Zürich)