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...

0:34:11

Low Diameter Graph Decompositions and Approximating Unique Games

Lap-Chi Lau, University of Waterloo
https://simons.berkeley.edu/talks/lap-chi-lau-09-14-17
Discrete Optimization via Continuous Relaxation
Visit talk page
0:54:31

A (1+epsilon)-approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies

Thomas Rothvoß, University of Washington
https://simons.berkeley.edu/talks/thomas-rothvoss-9-14-17
Discrete Optimization via Continuous Relaxation
Visit talk page
0:34:39

LP Relaxations for Reordering Buffer Management

Yuval Rabani, The Hebrew University of Jerusalem
https://simons.berkeley.edu/talks/yuval-rabani-09-15-17
Discrete Optimization via Continuous Relaxation
Visit talk page
0:26:10

Finding Best LP Relaxations for Various Cut Problems

Euiwoong Lee, Carnegie Mellon University
https://simons.berkeley.edu/talks/finding-best-lp-relaxations-various-cut-problems
Discrete Optimization via Continuous Relaxation
Visit talk page
0:58:13

A Survey of Dependent Rounding

Aravind Srinivasan, University of Maryland
https://simons.berkeley.edu/talks/aravind-srinivasan-9-11-17
Discrete Optimization via Continuous Relaxation
Visit talk page
0:34:27

Subdeterminant Maximization via Nonconvex Relaxations and Anti-concentration

Nisheeth Vishnoi, École Polytechnique Fédérale de Lausanne
https://simons.berkeley.edu/talks/subdeterminant-maximization-nonconvex-relaxations-and-anti-concentration
Discrete Optimization via Continuous Relaxation
Visit talk page
0:29:10

Approximating the Permanent of Positive Semidefinite Matrices

Nima Anari, Stanford University
https://simons.berkeley.edu/talks/nima-anari-09-15-17
Discrete Optimization via Continuous Relaxation
Visit talk page
0:28:11

Local Guarantees in Graph Cuts and Clustering

Moses Charikar, Stanford University
https://simons.berkeley.edu/talks/moses-charikar-09-15-17
Discrete Optimization via Continuous Relaxation
Visit talk page