Beyond Worst Case Analysis in Approximation

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=bX_ct_Uclk8


Duration: 56:56
520 views
3

Uri Feige, Weizmann Institute of Science
https://simons.berkeley.edu/talks/uri-feige-09-14-17
Discrete Optimization via Continuous Relaxation



Other Videos By Simons Institute for the Theory of Computing


2017-09-15Local Guarantees in Graph Cuts and Clustering
2017-09-15Approximating the Permanent of Positive Semidefinite Matrices
2017-09-15Subdeterminant Maximization via Nonconvex Relaxations and Anti-concentration
2017-09-15A Survey of Dependent Rounding
2017-09-15Finding Best LP Relaxations for Various Cut Problems
2017-09-14LP Relaxations for Reordering Buffer Management
2017-09-14A (1+epsilon)-approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies
2017-09-14Scheduling on Related Machines
2017-09-14Low Diameter Graph Decompositions and Approximating Unique Games
2017-09-14Algorithms for Stable and Perturbation-resilient Problems
2017-09-14Beyond Worst Case Analysis in Approximation
2017-09-13The Non-Uniform k-Center Problem
2017-09-13Online Optimization, Smoothing, and Competitive Ratio
2017-09-13A Nearly-linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
2017-09-13Submodular Unsplittable Flow on Trees
2017-09-13Submodular Optimization
2017-09-12LP Rounding for Poise
2017-09-12Improved Approximation for Non-preemptive Scheduling via Time-indexed LP Relaxations
2017-09-12Surviving in Directed Graphs: A Quasi-polynomial-time Polylogarithmic Approximation...
2017-09-12Compact, Provably-good LPs for Orienteering and Regret-bounded Vehicle Routing
2017-09-12A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem


Tags:
Simons Institute
Theory of Computing
Theory of Computation
Theoretical Computer Science
Computer Science
UC Berkeley
Discrete Optimization via Continuous Relaxation
Uri Feige