Discrete Optimization via Continuous Relaxation

Program

Bridging Continuous and Discrete Optimization

Location

Calvin Lab auditorium

Date

Monday, Sept. 11 – Friday, Sept. 15, 2017

Back to calendar

All presentations take place at the Calvin Lab Auditorium.

9 – 9:20 a.m.

Coffee and Check-In

9:20 – 9:30 a.m.

Opening Remarks

9:30 – 10:30 a.m.

The Power of Hierarchies for Detecting Hidden Structures

Prasad Raghavendra, UC Berkeley

10:30 – 11 a.m.

Break

11 – 11:30 a.m.

Simplex Transformations and Multiway Cut

Roy Schwartz, Technion - Israel Institute of Technology

11:30 a.m. – 12 p.m.

LPs and Convex Programming Relaxations and Rounding for Stochastic Problems

Anupam Gupta, Carnegie Mellon University

12 – 2 p.m.

Lunch

2 – 3 p.m.

Discrepancy and Approximation Algorithms

Sasho Nikolov, University of Toronto

3 – 3:30 p.m.

Break

3:30 – 4 p.m.

On Approximating the Covering Radius and Finding Dense Lattice Subspaces

Daniel Dadush, Centrum Wiskunde & Informatica

4 – 4:30 p.m.

A Strongly Polynomial Algorithm for Bimodular Integer Linear Programming

Rico Zenklusen, ETH Zürich

4:30 – 5:30 p.m.

Reception

9 – 9:30 a.m.

Coffee and Check-In

9:30 – 10:30 a.m.

Improved Approximation Algorithms for the TSP and S-t-path TSP

David Shmoys,
, Cornell University

10:30 – 11 a.m.

Break

11 a.m. – 12 p.m.

A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem

László Végh, London School of Economics

12 – 2 p.m.

Lunch

2 – 2:30 p.m.

Compact, Provably-good LPs for Orienteering and Regret-bounded Vehicle Routing

Chaitanya Swamy, University of Waterloo

2:30 – 3 p.m.

Surviving in Directed Graphs: A Quasi-polynomial-time Polylogarithmic Approximation for Two-connected Directed Steiner Tree

Fabrizio Grandoni, IDSIA, University of Lugano

3 – 3:30 p.m.

Break

3:30 – 4 p.m.

Improved Approximation for Non-preemptive Scheduling via Time-indexed LP Relaxations

Shi Li, SUNY Buffalo

4 – 4:30 p.m.

LP Rounding for Poise

R. Ravi, Carnegie Mellon University

4:30 – 5:30 p.m.

Lightning Talks

9 – 9:30 a.m.

Coffee and Check-In

9:30 – 10:30 a.m.

Submodular Optimization

Niv Buchbinder, Tel Aviv University

10:30 – 11 a.m.

Break

11 – 11:30 a.m.

Submodular Unsplittable Flow on Trees

Anna Adamaszek, University of Copenhagen

11:30 a.m. – 12 p.m.

A Nearly-linear Time Algorithm for Submodular Maximization with a Knapsack Constraint

Alina Ene, Boston University

12 – 2 p.m.

Lunch

2 – 3 p.m.

Online Optimization, Smoothing, and Competitive Ratio

Maryam Fazel, University of Washington

3 – 3:30 p.m.

Break

3:30 – 4 p.m.

The Non-Uniform k-Center Problem

Deeparnab Chakrabarty (Dartmouth College)

4 – 4:30 p.m.

Scheduling on Related Machines

Debmalya Panigrahi, Duke University

9 – 9:30 a.m.

Coffee and Check-In

9:30 – 10:30 a.m.

Beyond Worst Case Analysis in Approximation

Uri Feige, Weizmann Institute of Science

10:30 – 11 a.m.

Break

11 – 11:30 a.m.

Algorithms for Stable and Perturbation-resilient Problems

Kostya Makarychev, Northwestern University

11:30 a.m. – 12 p.m.

Low Diameter Graph Decompositions and Approximating Unique Games

Lap-Chi Lau, University of Waterloo

12 – 2 p.m.

Lunch

2 – 3 p.m.

A (1+epsilon)-approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies

Thomas Rothvoß, University of Washington

3 – 3:30 p.m.

Break

3:30 – 4 p.m.

LP Relaxations for Reordering Buffer Management

Yuval Rabani, The Hebrew University of Jerusalem

4 – 4:30 p.m.

Finding Best LP Relaxations for Various Cut Problems

Euiwoong Lee, Carnegie Mellon University

9 – 9:30 a.m.

Coffee and Check-In

9:30 – 10:30 a.m.

A Survey of Dependent Rounding

Aravind Srinivasan,,
University of Maryland

10:30 – 11 a.m.

Break

11 – 11:30 a.m.

Subdeterminant Maximization via Nonconvex Relaxations and Anti-concentration

Nisheeth Vishnoi, École Polytechnique Fédérale de Lausanne

11:30 a.m. – 12 p.m.

Approximating the Permanent of Positive Semidefinite Matrices

Nima Anari,
, Stanford University

12 – 12:30 p.m.

Local Guarantees in Graph Cuts and Clustering

Moses Charikar, Stanford University