Completed
We want approximate: allow some slack
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Near-Optimal Fully Dynamic Densest Subgraph
Automatically move to the next video in the Classroom when playback concludes
- 1 Intro
- 2 Overview
- 3 Dense subgraphs
- 4 Motivation - correlation mining
- 5 Motivation - fraud detection
- 6 Motivation - story identification
- 7 Definition of density
- 8 Algorithms for static densest subgraph
- 9 Why dynamic algorithms
- 10 Our goal - fully dynamic algorithm for Densest Subgraph
- 11 Algorithms for dynamic densest subgraph
- 12 LP formulation
- 13 Dual of the LP
- 14 Dual LP: load balancing visualization
- 15 Dual LP: local optimality
- 16 We want approximate: allow some slack
- 17 Visualize as graph orientation problem
- 18 Dynamic graph orientation
- 19 Bounding number of flips
- 20 Dealing with dynamic
- 21 Runtime
- 22 Recap
