MIT 6.854 Spring 2016 Lecture 19: Semidefinite Programming, MAXCUT

preview_player
Показать описание

  1. Andrew Xia
Рекомендации по теме
MIT 6.854 Spring 0:59:17

MIT 6.854 Spring 2016 Lecture 3: Consistent Hashing and Random Trees

University of Texas 0:19:27

University of Texas at Austin 2014 Commencement Address - Admiral William H. McRaven

New Jersey are 0:01:00

New Jersey are you ready? TO RECEIVE THE MINISTRY OF PROPHET VICTOR KUSI BOATENG!

StatMolThermo 07.04 Entropy 0:12:47

StatMolThermo 07.04 Entropy From the Partition Function

Celebration of Mike 0:37:12

Celebration of Mike Stonebraker #8 - Students (Magda Balazinska, Andy Pavlo)

ExquizOn S6 Mini 0:09:26

ExquizOn S6 Mini Cube DLP Pocket Projector Miracast Airplay 100 lumens

The Genealogy of 0:59:01

The Genealogy of the Milky Way and the Search for Dark Matter

Nmap.exe Demystified: The 0:30:32

Nmap.exe Demystified: The Ultimate Network Discovery Tool Part 1

MAX BILL, JOSEPH 1:02:36

MAX BILL, JOSEPH MARIA OLBRICH | ICARCH 2022

2020_05_12_Jonathan Home: 'Quantum 0:50:07

2020_05_12_Jonathan Home: 'Quantum computing with trapped ions'

'Fault tolerance made 0:43:06

'Fault tolerance made easy' by Uwe Friedrichsen - Coding Serbia Conference

NICO101 - Mac 0:03:43

NICO101 - Mac OS X Anaconda Installation

20160913 introduction 0:57:56

20160913 introduction

RNA Collaborative Seminar 1:04:23

RNA Collaborative Seminar Series, Yale August 26, 2020

Applying data science 1:03:01

Applying data science in healthcare with Muhammad Mamdani (Unity Health Toronto)

Awakening Our Democracy: 1:38:40

Awakening Our Democracy: Affirmative Action

MPG Primer: A 0:45:01

MPG Primer: A Practical guide to bulk RNA-seq, including guidelines for eQTL analysis (2024)

John Rawls--Modern Political 0:54:22

John Rawls--Modern Political Philosophy--Lecture 8 (audio only)

General Aptitude GATE 1:20:53

General Aptitude GATE - 2023 | Question of the Day - 42 | Sanga N L N Sarma | Kreatryx GATE

Privacy in ML: 0:55:28

Privacy in ML: Introduction to Differential Privacy

Physics Daily Practice 0:42:05

Physics Daily Practice Paper (DPP) Series | Physics Practice for NDA/AirforceXY/Navy 2021 | RS Jyani

Комментарии
Автор

4:50 - 13:30 MAXCUT problem (phrasing it as an (fractional) LP doesn't solve it more precisely than naive approximation algo with flipping a fair coin)
13:30 - 23:30 positive semidefinite (PSD) definition and SDP (semidefinite programming)
23:30 - 35:40 building intuition
35:40 - 41:20 lemma 1 (used for proving weak duality and another way of defining what a PSD is)
43:35 - 46:35 lemma 2 aka weak duality
47:15 - 49:50 strong duality "usually" holds (Slater's condition)
50:45 - 58:10 MAXCUT problem now solved using SDP
58:10 - 1:12:30 Goemans-Williamson theorem/analysis
1:12:30 UGC - unique game conjecture

aleksagordic
Автор

Students in this class are well prepared.

wuzhai