Approximation Algorithms and the Hardness of Approximation

Videos from BIRS Workshop

, University of Washington
- 09:38
Effective Resistance Flows and Asymmetric TSP
Watch video | Download video: 201408040903-OveisGharan.mp4 (146M)
, University of Bonn
- 10:09
Ears and tours
Watch video | Download video: 201408040939-Vygen.mp4 (81M)
, Microsoft Research, Redmond
- 10:38
Computability of maximum entropy distributions and counting problems
Watch video | Download video: 201408041011-Singh.mp4 (78M)
, École polytechnique fédérale de Lausanne
- 12:06
LP-Based algorithms for capacitated facility location
Watch video | Download video: 201408041105-An.mp4 (173M)
, Carnegie Mellon University
- 17:02
Deliver or hold: Approximation algorithms for the periodic inventory routing problem
Watch video | Download video: 201408041637-Ravi.mp4 (79M)
, Toyota Technological Institute at Chicago
- 09:40
Nonuniform graph partitioning with unrelated weights
Watch video | Download video: 201408050910-Makarychev.mp4 (110M)
, Northwestern University
- 10:13
Constant factor approximation for balanced cut in the PIE model Tasos Sidiropoulos: Spectral concentration, robust k-center, and simple clustering
Watch video | Download video: 201408050941-Makarychev.mp4 (90M)
, University of Illinois at Chicago
- 10:41
Spectral concentration, robust k-center, and simple clustering
Watch video | Download video: 201408051018-Sidiropoulos.mp4 (70M)
, University of California Berkeley
- 11:56
On the power of symmetric LP/SDP relaxations
Watch video | Download video: 201408051104-Raghavendra.mp4 (161M)
, École Polytechnique Fédérale de Lausanne
- 16:36
TSP on regular graphs and beyond
Watch video | Download video: 201408051607-Vishnoi.mp4 (73M)
, University of Waterloo
- 17:09
Region-growing and combinatorial algorithms for k-route cut problems
Watch video | Download video: 201408051637-Swamy.mp4 (99M)
, EPFL
- 17:42
Combinatorial algorithm for restricted max-min fair allocation
Watch video | Download video: 201408051709-Svensson.mp4 (99M)
, IBM Almaden Research Center
- 10:08
Approximability of multiway partitioning problems and lower bounds from Sperner’s colorings
Watch video | Download video: 201408060934-Vondrak.mp4 (89M)
, KTH Royal Institute of Technology
- 10:39
(2+ε)-SAT is NP-hard
Watch video | Download video: 201408061008-Austrin.mp4 (125M)
, Weizmann Institute
- 12:03
Open questions in parallel repetition of games and PCPs
Watch video | Download video: 201408061105-Dinur.mp4 (225M)
, Princeton University
- 09:39
Smoothed analysis of tensor decompositions
Watch video | Download video: 201408070905-Charikar.mp4 (133M)
, College of William and Mary
- 10:08
On some recent MAX SAT approximation algorithms
Watch video | Download video: 201408070940-vanZuylen.mp4 (74M)
, Cornell University
- 10:36
Limitations of greedy algorithms for MAX SAT
Watch video | Download video: 201408071009-Poloczek.mp4 (80M)
, Cornell University
- 12:13
Sum-of-squares method, tensor decomposition, and dictionary learning
Watch video | Download video: 201408071105-Steurer.mp4 (202M)
, University of Washington
- 16:34
Constructive discrepancy minimization for convex sets
Watch video | Download video: 201408071603-Rothvoss.mp4 (96M)
, University of Washington
- 17:07
Talagrand’s convolution conjecture and anti-concentration of smoothed functions
Watch video | Download video: 201408071635-Lee.mp4 (92M)
, University of Alberta
- 09:37
Approximation Algorithms for Minimum-Load k-Facility Location
Watch video | Download video: 201408080905-Salavatipour.mp4 (78M)
, University of Illinois, Urbana-Champaign
- 10:10
Routing and Treewidth
Watch video | Download video: 201408080938-Chekuri.mp4 (81M)