Playlist: 28 videos

Discrete Optimization via Continuous Relaxation

Much of the progress in solving discrete optimization problems, especially in terms of approximation algorithms, has come from designing novel continuous relaxations. The primary tools in this area are linear programming and semidefinite programming...

1:7:15

The Power of Hierarchies for Detecting Hidden Structures

Prasad Raghavendra, UC Berkeley
https://simons.berkeley.edu/talks/prasad-raghavendra-09-11-17
Discrete Optimization via Continuous Relaxation
Visit talk page
0:33:25

Simplex Transformations and Multiway Cut

Roy Schwartz, Technion - Israel Institute of Technology
https://simons.berkeley.edu/talks/roy-schwartz-9-11-17
Discrete Optimization via Continuous Relaxation
Visit talk page
0:31:45

LPs and Convex Programming Relaxations and Rounding for Stochastic Problems

Anupam Gupta, Carnegie Mellon University
https://simons.berkeley.edu/talks/anupam-gupta-09-11-17
Discrete Optimization via Continuous Relaxation
Visit talk page
1:3:56

Discrepancy and Approximation Algorithms

Sasho Nikolov, University of Toronto
https://simons.berkeley.edu/talks/sasho-nikolov-09-11-17
Discrete Optimization via Continuous Relaxation
Visit talk page
0:31:42

On Approximating the Covering Radius and Finding Dense Lattice Subspaces

Daniel Dadush, Centrum Wiskunde & Informatica
https://simons.berkeley.edu/talks/daniel-dadush-09-11-17
Discrete Optimization via Continuous Relaxation
Visit talk page
0:31:35

A Strongly Polynomial Algorithm for Bimodular Integer Linear Programming

Rico Zenklusen, ETH Zürich
https://simons.berkeley.edu/talks/rico-zenklusen-09-11-17
Discrete Optimization via Continuous Relaxation
Visit talk page
1:1:27

Improved Approximation Algorithms for the TSP and S-t-path TSP

David Shmoys, Cornell University
https://simons.berkeley.edu/talks/david-shmoys-09-12-17
Discrete Optimization via Continuous Relaxation
Visit talk page
1:7:59

A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem

László Végh, London School of Economics
https://simons.berkeley.edu/talks/laszlo-vegh-09-12-17
Discrete Optimization via Continuous Relaxation
Visit talk page
0:30:12

Compact, Provably-good LPs for Orienteering and Regret-bounded Vehicle Routing

Chaitanya Swamy, University of Waterloo
https://simons.berkeley.edu/talks/chaitanya-swamy-09-12-17
Discrete Optimization via Continuous Relaxation
Visit talk page
0:28:28

Surviving in Directed Graphs: A Quasi-polynomial-time Polylogarithmic Approximation for Two-connected Directed Steiner Tree

Fabrizio Grandoni, IDSIA, University of Lugano
https://simons.berkeley.edu/talks/fabrizio-grandoni-09-12-17
Discrete Optimization via Continuous Relaxation
Visit talk page