Approximation Algorithms and the Hardness of Approximation
Videos from BIRS Workshop
Rico Zenklusen, ETH Zurich
Monday Nov 13, 2017 09:05 - 10:05
Bimodular Integer Linear Programming and Beyond
Chaitanya Swamy, University of Waterloo
Monday Nov 13, 2017 10:30 - 11:02
Improved Algorithms for MST and Metric-TSP Interdiction
Cedric Koh, University of Waterloo
Monday Nov 13, 2017 11:03 - 11:29
Stabilizing Weighted Graphs
Yury Makarychev, Toyota Technological Institute at Chicago
Monday Nov 13, 2017 15:34 - 16:05
Algorithms for Stable and Perturbation-Resilient Problems
Parinya Chalermsook, Aalto University
Monday Nov 13, 2017 16:07 - 16:35
From Gap-ETH to FPT Inapproximability: Clique, Dominating Set, and More
Bundit Laekhanukit, Shanghai University of Finance and Economics
Monday Nov 13, 2017 16:38 - 17:03
(Almost) Settling the Complexity of Approximating Parameterized Dominating Set.
Shayan Oveis Gharan, University of Washington
Tuesday Nov 14, 2017 09:02 - 09:50
A Simply Exponential upper bound on the Number of Stable Matchings
Amin Saberi, Stanford University
Tuesday Nov 14, 2017 10:30 - 10:58
Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices
James R. Lee, University of Washington
Tuesday Nov 14, 2017 11:02 - 11:35
k-server via multi-scale entropic regulariziation
Fabrizio Grandoni, IDSIA, University of Lugano
Tuesday Nov 14, 2017 11:37 - 12:04
Surviving in Directed Graphs: A Quasi-polynomial-time Polylogarithmic Approximation for Two-connected Directed Steiner Tree
Alina Ene, Boston University
Tuesday Nov 14, 2017 15:56 - 16:31
Faster algorithms for line search in the submodular base polytope
Laura Sanita, Comb. and Opt. -- University of Waterloo
Tuesday Nov 14, 2017 16:32 - 17:01
Approximating Weighted Tree Augmentation via Chvatal-Gomory Cuts
Michael Dinitz, Johns Hopkins University
Wednesday Nov 15, 2017 09:03 - 09:56
Approximating spanners and distance oracles.
Samuel Hopkins, Cornell University
Wednesday Nov 15, 2017 10:31 - 11:02
Learning mixtures of Gaussians under much less separation
Konstantin Makarychev, Northwestern University
Wednesday Nov 15, 2017 11:03 - 11:32
Learning Communities in the Presence of Errors
Shuchi Chawla, University of Wisconsin-Madison
Wednesday Nov 15, 2017 11:34 - 12:08
Online Stochastic Scheduling using Posted Prices
Zachary Friggstad, University of Alberta
Thursday Nov 16, 2017 09:03 - 09:58
Approximation Schemes for Clustering Problems: Now With Outliers
Viswanath Nagarajan, University of Michigan
Thursday Nov 16, 2017 10:31 - 11:01
Online Covering with Sum of Lq-norm Objectives
Sam Gutekunst, Cornell University
Thursday Nov 16, 2017 11:02 - 11:23
Semidefinite Programming Relaxations of the Traveling Salesman Problem
Rachit Nimavat, Toyota Technological Institute at Chicago
Thursday Nov 16, 2017 15:32 - 16:01
Almost Polynomial Hardness of Node-Disjoint Paths in Grids
Madhur Tulsiani, Toyota Technological Institute at Chicago
Thursday Nov 16, 2017 16:02 - 16:30
From Weak to Strong LP Gaps for all CSPs
Tselil Schramm, Stanford
Thursday Nov 16, 2017 16:32 - 17:02
Sum-of-squares $\equiv_{avg}$ Spectral Algorithms
Lap Chi Lau, University of Waterloo
Friday Nov 17, 2017 09:03 - 10:04
The Paulsen problem, continuous operator scaling, and smoothed analysis
