Approximation Algorithms and the Hardness of Approximation

Videos from BIRS Workshop 17w5133

, ETH Zurich
- 10:05
Bimodular Integer Linear Programming and Beyond
Watch video | Download video: 201711130905-Zenklusen.mp4 (196M)
, University of Waterloo
- 11:02
Improved Algorithms for MST and Metric-TSP Interdiction
Watch video | Download video: 201711131030-Swamy.mp4 (126M)
, University of Waterloo
- 11:29
Stabilizing Weighted Graphs
Watch video | Download video: 201711131103-Koh.mp4 (116M)
, Toyota Technological Institute at Chicago
- 16:05
Algorithms for Stable and Perturbation-Resilient Problems
Watch video | Download video: 201711131534-Makarychev.mp4 (100M)
, Aalto University
- 16:35
From Gap-ETH to FPT Inapproximability: Clique, Dominating Set, and More
Watch video | Download video: 201711131607-Chalermsook.mp4 (80M)
, Simons Institute for the Theory of Computing & Shanghai University of Finance and Economics
- 17:03
(Almost) Settling the Complexity of Approximating Parameterized Dominating Set.
Watch video | Download video: 201711131638-Laekhanukit.mp4 (75M)
, University of Washington
- 09:50
A Simply Exponential upper bound on the Number of Stable Matchings
Watch video | Download video: 201711140902-OveisGharan.mp4 (195M)
, Stanford University
- 10:58
Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices
Watch video | Download video: 201711141030-Saberi.mp4 (157M)
, University of Washington
- 11:35
k-server via multi-scale entropic regulariziation
Watch video | Download video: 201711141102-Lee.mp4 (113M)
, IDSIA, University of Lugano
- 12:04
Surviving in Directed Graphs: A Quasi-polynomial-time Polylogarithmic Approximation for Two-connected Directed Steiner Tree
Watch video | Download video: 201711141137-Grandoni.mp4 (127M)
, Boston University
- 16:31
Faster algorithms for line search in the submodular base polytope
Watch video | Download video: 201711141556-Ene.mp4 (105M)
, University of Waterloo
- 17:01
Approximating Weighted Tree Augmentation via Chvatal-Gomory Cuts
Watch video | Download video: 201711141632-Sanita.mp4 (166M)
, Johns Hopkins University
- 09:56
Approximating spanners and distance oracles.
Watch video | Download video: 201711150903-Dinitz.mp4 (171M)
, Cornell University
- 11:02
Learning mixtures of Gaussians under much less separation
Watch video | Download video: 201711151031-Hopkins.mp4 (123M)
, Northwestern University
- 11:32
Learning Communities in the Presence of Errors
Watch video | Download video: 201711151103-Makarychev.mp4 (141M)
, University of Wisconsin-Madison
- 12:08
Online Stochastic Scheduling using Posted Prices
Watch video | Download video: 201711151134-Chawla.mp4 (117M)
, University of Alberta
- 09:58
Approximation Schemes for Clustering Problems: Now With Outliers
Watch video | Download video: 201711160903-Friggstad.mp4 (177M)
, University of Michigan
- 11:01
Online Covering with Sum of Lq-norm Objectives
Watch video | Download video: 201711161031-Nagarajan.mp4 (97M)
, Cornell University
- 11:23
Semidefinite Programming Relaxations of the Traveling Salesman Problem
Watch video | Download video: 201711161102-Gutekunst.mp4 (80M)
, Toyota Technological Institute at Chicago
- 16:01
Almost Polynomial Hardness of Node-Disjoint Paths in Grids
Watch video | Download video: 201711161532-Nimavat.mp4 (76M)
, Toyota Technological Institute at Chicago
- 16:30
From Weak to Strong LP Gaps for all CSPs
Watch video | Download video: 201711161602-Tulsiani.mp4 (98M)
, Harvard/MIT
- 17:02
Sum-of-squares $\equiv_{avg}$ Spectral Algorithms
Watch video | Download video: 201711161632-Schramm.mp4 (85M)
, University of Waterloo
- 10:04
The Paulsen problem, continuous operator scaling, and smoothed analysis
Watch video | Download video: 201711170903-Lau.mp4 (332M)