Workshops

Fall 2017

Discrete Optimization via Continuous Relaxation

Sep 11, 2017 to Sep 15, 2017

Return to event »

All presentations take place at the Calvin Lab Auditorium.

Monday, September 11th, 2017
9:00 am–9:20 am		Coffee and Check-In
9:20 am–9:30 am		Opening Remarks
9:30 am–10:30 am		The Power of Hierarchies for Detecting Hidden Structures Prasad Raghavendra, UC Berkeley
10:30 am–11:00 am		Break
11:00 am–11:30 am		Simplex Transformations and Multiway Cut Roy Schwartz, Technion - Israel Institute of Technology
11:30 am–12:00 pm		LPs and Convex Programming Relaxations and Rounding for Stochastic Problems Anupam Gupta, Carnegie Mellon University
12:00 pm–2:00 pm		Lunch
2:00 pm–3:00 pm		Discrepancy and Approximation Algorithms Sasho Nikolov, University of Toronto
3:00 pm–3:30 pm		Break
3:30 pm–4:00 pm		On Approximating the Covering Radius and Finding Dense Lattice Subspaces Daniel Dadush, Centrum Wiskunde & Informatica
4:00 pm–4:30 pm		A Strongly Polynomial Algorithm for Bimodular Integer Linear Programming Rico Zenklusen, ETH Zürich
4:30 pm–5:30 pm		Reception

Tuesday, September 12th, 2017
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:30 am		Improved Approximation Algorithms for the TSP and S-t-path TSP David Shmoys , Cornell University
10:30 am–11:00 am		Break
11:00 am–12:00 pm		A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem László Végh, London School of Economics
12:00 pm–2:00 pm		Lunch
2:00 pm–2:30 pm		Compact, Provably-good LPs for Orienteering and Regret-bounded Vehicle Routing Chaitanya Swamy, University of Waterloo
2:30 pm–3:00 pm		Surviving in Directed Graphs: A Quasi-polynomial-time Polylogarithmic Approximation for Two-connected Directed Steiner Tree Fabrizio Grandoni, IDSIA, University of Lugano
3:00 pm–3:30 pm		Break
3:30 pm–4:00 pm		Improved Approximation for Non-preemptive Scheduling via Time-indexed LP Relaxations Shi Li, SUNY Buffalo
4:00 pm–4:30 pm		LP Rounding for Poise R. Ravi, Carnegie Mellon University
4:30 pm–5:30 pm		Lightning Talks

Wednesday, September 13th, 2017
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:30 am		Submodular Optimization Niv Buchbinder, Tel Aviv University
10:30 am–11:00 am		Break
11:00 am–11:30 am		Submodular Unsplittable Flow on Trees Anna Adamaszek, University of Copenhagen
11:30 am–12:00 pm		A Nearly-linear Time Algorithm for Submodular Maximization with a Knapsack Constraint Alina Ene, Boston University
12:00 pm–2:00 pm		Lunch
2:00 pm–3:00 pm		Online Optimization, Smoothing, and Competitive Ratio Maryam Fazel, University of Washington
3:00 pm–3:30 pm		Break
3:30 pm–4:00 pm		The Non-Uniform k-Center Problem Deeparnab Chakrabarty, Dartmouth College
4:00 pm–4:30 pm		Scheduling on Related Machines Debmalya Panigrahi, Duke University

Thursday, September 14th, 2017
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:30 am		Beyond Worst Case Analysis in Approximation Uri Feige, Weizmann Institute of Science
10:30 am–11:00 am		Break
11:00 am–11:30 am		Algorithms for Stable and Perturbation-resilient Problems Kostya Makarychev, Northwestern University
11:30 am–12:00 pm		Low Diameter Graph Decompositions and Approximating Unique Games Lap-Chi Lau, University of Waterloo
12:00 pm–2:00 pm		Lunch
2:00 pm–3:00 pm		A (1+epsilon)-approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies Thomas Rothvoß, University of Washington
3:00 pm–3:30 pm		Break
3:30 pm–4:00 pm		LP Relaxations for Reordering Buffer Management Yuval Rabani, The Hebrew University of Jerusalem
4:00 pm–4:30 pm		Finding Best LP Relaxations for Various Cut Problems Euiwoong Lee, Carnegie Mellon University

Friday, September 15th, 2017
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:30 am		A Survey of Dependent Rounding Aravind Srinivasan, University of Maryland
10:30 am–11:00 am		Break
11:00 am–11:30 am		Subdeterminant Maximization via Nonconvex Relaxations and Anti-concentration Nisheeth Vishnoi, École Polytechnique Fédérale de Lausanne
11:30 am–12:00 pm		Approximating the Permanent of Positive Semidefinite Matrices Nima Anari , Stanford University
12:00 pm–12:30 pm		Local Guarantees in Graph Cuts and Clustering Moses Charikar, Stanford University