Approximation Algorithms and the Hardness of Approximation
Videos from BIRS Workshop
Shayan Oveis Gharan, University of Washington
Monday Aug 4, 2014 09:03 - 09:38
Effective Resistance Flows and Asymmetric TSP
Jens Vygen, University of Bonn
Monday Aug 4, 2014 09:39 - 10:09
Ears and tours
Mohit Singh, Microsoft Research, Redmond
Monday Aug 4, 2014 10:11 - 10:38
Computability of maximum entropy distributions and counting problems
Hyung-Chan An, École polytechnique fédérale de Lausanne
Monday Aug 4, 2014 11:05 - 12:06
LP-Based algorithms for capacitated facility location
Ramamoorthi Ravi, Carnegie Mellon University
Monday Aug 4, 2014 16:37 - 17:02
Deliver or hold: Approximation algorithms for the periodic inventory routing problem
Yury Makarychev, Toyota Technological Institute at Chicago
Tuesday Aug 5, 2014 09:10 - 09:40
Nonuniform graph partitioning with unrelated weights
Konstantin Makarychev, Northwestern University
Tuesday Aug 5, 2014 09:41 - 10:13
Constant factor approximation for balanced cut in the PIE model Tasos Sidiropoulos: Spectral concentration, robust k-center, and simple clustering
Anatasios Sidiropoulos, University of Illinois at Chicago
Tuesday Aug 5, 2014 10:18 - 10:41
Spectral concentration, robust k-center, and simple clustering
Prasad Raghavendra, University of California Berkeley
Tuesday Aug 5, 2014 11:04 - 11:56
On the power of symmetric LP/SDP relaxations
Nisheeth Vishnoi, École Polytechnique Fédérale de Lausanne
Tuesday Aug 5, 2014 16:07 - 16:36
TSP on regular graphs and beyond
Chaitanya Swamy, University of Waterloo
Tuesday Aug 5, 2014 16:37 - 17:09
Region-growing and combinatorial algorithms for k-route cut problems
Ola Svensson, EPFL
Tuesday Aug 5, 2014 17:09 - 17:42
Combinatorial algorithm for restricted max-min fair allocation
Jan Vondrak, IBM Almaden Research Center
Wednesday Aug 6, 2014 09:34 - 10:08
Approximability of multiway partitioning problems and lower bounds from Sperner’s colorings
Per Austrin, KTH Royal Institute of Technology
Wednesday Aug 6, 2014 10:08 - 10:39
(2+ε)-SAT is NP-hard
Irit Dinur, Weizmann Institute
Wednesday Aug 6, 2014 11:05 - 12:03
Open questions in parallel repetition of games and PCPs
Moses Charikar, Princeton University
Thursday Aug 7, 2014 09:05 - 09:39
Smoothed analysis of tensor decompositions
Anke van Zuylen, College of William and Mary
Thursday Aug 7, 2014 09:40 - 10:08
On some recent MAX SAT approximation algorithms
Matthias Poloczek, Cornell University
Thursday Aug 7, 2014 10:09 - 10:36
Limitations of greedy algorithms for MAX SAT
David Steurer, Cornell University
Thursday Aug 7, 2014 11:05 - 12:13
Sum-of-squares method, tensor decomposition, and dictionary learning
Thomas Rothvoss, University of Washington
Thursday Aug 7, 2014 16:03 - 16:34
Constructive discrepancy minimization for convex sets
James R. Lee, University of Washington
Thursday Aug 7, 2014 16:35 - 17:07
Talagrand’s convolution conjecture and anti-concentration of smoothed functions
Mohammad Salavatipour, University of Alberta
Friday Aug 8, 2014 09:05 - 09:37
Approximation Algorithms for Minimum-Load k-Facility Location
Chandra Chekuri, University of Illinois, Urbana-Champaign
Friday Aug 8, 2014 09:38 - 10:10
Routing and Treewidth