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:30:26

Improved Approximation for Non-preemptive Scheduling via Time-indexed LP Relaxations

Shi Li, SUNY Buffalo
https://simons.berkeley.edu/talks/shi-li-09-15-17
Discrete Optimization via Continuous Relaxation
Visit talk page
0:32:19

LP Rounding for Poise

R. Ravi, Carnegie Mellon University
https://simons.berkeley.edu/talks/r-ravi-09-12-17
Discrete Optimization via Continuous Relaxation
Visit talk page
0:59:18

Submodular Optimization

Niv Buchbinder, Tel Aviv University
https://simons.berkeley.edu/talks/niv-buchbinder-09-13-17
Discrete Optimization via Continuous Relaxation
Visit talk page
0:29:26

Submodular Unsplittable Flow on Trees

Anna Adamaszek, University of Copenhagen
https://simons.berkeley.edu/talks/anna-adamaszek-09-13-17
Discrete Optimization via Continuous Relaxation
Visit talk page
0:33:3

A Nearly-linear Time Algorithm for Submodular Maximization with a Knapsack Constraint

Alina Ene, Boston University
https://simons.berkeley.edu/talks/alina-ene-09-13-17
Discrete Optimization via Continuous Relaxation
Visit talk page
1:0:56

Online Optimization, Smoothing, and Competitive Ratio

Maryam Fazel, University of Washington
https://simons.berkeley.edu/talks/maryam-fazel-09-13-17
Discrete Optimization via Continuous Relaxation
Visit talk page
0:32:13

The Non-Uniform k-Center Problem

Deeparnab Chakrabarty, Dartmouth College
https://simons.berkeley.edu/talks/deeparnab-chakrabarty-09-13-17
Discrete Optimization via Continuous Relaxation
Visit talk page
0:29:25

Scheduling on Related Machines

Debmalya Panigrahi, Duke University
https://simons.berkeley.edu/talks/debmalya-panigrahi-09-13-17
Discrete Optimization via Continuous Relaxation
Visit talk page
0:56:56

Beyond Worst Case Analysis in Approximation

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

Algorithms for Stable and Perturbation-resilient Problems

Kostya Makarychev, Northwestern University
https://simons.berkeley.edu/talks/kostya-makarychev-09-14-17
Discrete Optimization via Continuous Relaxation
Visit talk page