Approximation Algorithms and the Hardness of Approximation
Videos from BIRS Workshop
Vera Traub, University of Bonn
Monday Sep 18, 2023 09:02 - 10:02
Approximating Weighted Connectivity Augmentation below Factor 2
Neil Olver, London School of Economics and Political Science
Monday Sep 18, 2023 10:31 - 11:04
Thin Trees for Laminar Families
Rhea Jain, University of Illinois at Urbana Champaign
Monday Sep 18, 2023 11:06 - 11:30
Approximation Algorithms for Network Design in Non-Uniform Fault Models
Ishan Bansal, Cornell University
Monday Sep 18, 2023 16:02 - 16:30
Edge-Augmentation Beyond Uncrossable Families
Daniel Hathcock, Carnegie Mellon University
Monday Sep 18, 2023 16:30 - 17:00
One Tree to Rule Them All: Poly-Logarithmic Universal Steiner Tree
Ramin Mousavi, University of Alberta
Monday Sep 18, 2023 17:01 - 17:22
Some progress in directed Steiner tree on planar graphs
Amey Bhangale, University of California, Riverside
Tuesday Sep 19, 2023 08:48 - 09:30
On Approximability of Satisfiable CSPs
Dana Moshkovitz, University of Texas at Austin
Tuesday Sep 19, 2023 09:35 - 10:05
Almost Chor-Goldreich Sources and Adversarial Random Walks
Suprovat Ghoshal, Northwestern University & TTIC
Tuesday Sep 19, 2023 10:37 - 11:10
A Characterization of Approximability for Biased CSPs
Joshua Brakensiek, Stanford University
Tuesday Sep 19, 2023 11:11 - 11:30
New Approximability Results for MAX CSPs
David Shmoys, Cornell University
Tuesday Sep 19, 2023 15:03 - 15:35
The Joint Replenishment Problem with Outliers, and with Fairness Constraints
Thomas Rothvoss, University of Washington
Tuesday Sep 19, 2023 16:01 - 16:32
The Subspace Flatness Conjecture and Faster Integer Programming
Seffi Naor, Technion
Tuesday Sep 19, 2023 16:33 - 17:01
Rounding Bipartite Matchings
Dor Minzer, Massachusetts Institute of Technology
Tuesday Sep 19, 2023 17:02 - 17:36
On Abelian Embeddings, Parallel Repetition and the GHZ game
Nicole Megow, University of Bremen
Wednesday Sep 20, 2023 08:47 - 09:31
Set Selection under Explorable Stochastic Uncertainty via Covering Techniques
Jens Vygen, University of Bonn
Wednesday Sep 20, 2023 09:31 - 10:04
Improved guarantees for the a priori TSP
David Williamson, Cornell University
Wednesday Sep 20, 2023 10:31 - 11:02
A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the Traveling Salesman Problem
Xuandi Ren, University of California, Berkeley
Wednesday Sep 20, 2023 11:03 - 11:30
Baby PIH: Parameterized Inapproximability of Min CSP
Joseph Cheriyan, University of Waterloo
Wednesday Sep 20, 2023 11:31 - 12:04
Algorithms for 2-connected network design and flexible Steiner trees with a constant number of terminals
Shi Li, Nanjing University
Wednesday Sep 20, 2023 16:37 - 17:09
Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering
Jaroslaw Byrka, University of Wrocław
Wednesday Sep 20, 2023 17:10 - 17:33
An O(loglog n)-Approximation for Submodular Facility Location
Deeparnab Chakrabarty, Dartmouth College
Thursday Sep 21, 2023 08:48 - 09:33
Round-or-Cut Technique for designing Approximation Algorithms for Clustering Problems
Chaitanya Swamy, University of Waterloo
Thursday Sep 21, 2023 09:34 - 10:14
Stochastic Minimum-Norm Combinatorial Optimization
Konstantin Makarychev, Northwestern University
Friday Sep 22, 2023 09:03 - 09:37
Explainable Clustering
Venkatesan Guruswami, UC Berkeley
Friday Sep 22, 2023 09:37 - 10:08
SDPs and Robust Satisfiability of Promise CSP
Lap Chi Lau, University of Waterloo
Friday Sep 22, 2023 11:00 - 11:41
Cheeger-Type Inequalities Using Reweighted Eigenvalues
