en
0.25
0.5
0.75
1.25
1.5
1.75
2
The Primal-Dual approach for Online Algorithms
Published on Oct 02, 20125241 Views
Online algorithms deal with settings where the input data arrives over time and the current decision must be made by the algo- rithm without the knowledge of future input. In the last few years, the
Related categories
Chapter list
A Primal-Dual Approach for Online Problems00:00
Outline00:06
Online Algorithms00:37
Randomized Algorithms02:25
Some classic problems04:36
The Ski Rental Problem04:43
Online Virtual Circuit Routing06:14
Virtual Circuit Routing - Example07:09
Virtual Circuit Routing07:33
The Paging/Caching Problem08:55
Previous Results: Paging10:18
Do these problems have anything in common?11:02
An Abstract Online Problem11:20
Example13:12
The Dual Problem14:51
Ski Rental – Integer Program16:30
Routing – Linear Program17:12
Paging – Linear Program18:10
What can we say about the abstract problem ?21:39
General Covering/Packing Results (1)21:40
General Covering/Packing Results (2)23:41
Consequences24:15
Rest of the Talk26:12
Duality (1)27:01
Duality (2)27:48
LP Duality29:37
Offline Primal-Dual Approach34:24
Key Idea for Online Primal Dual35:44
How to initialize41:50
The Algorithm43:48
Example: Weighted Caching45:35
Generalized Caching48:48
Part 2: Rounding (1)51:07
Part 2: Rounding (2)52:45
Beyond Packing/Covering LPs55:37
Extended Framework55:48
New LP for weighted paging57:22
Result58:22
Our Approach58:28
Analysis59:07
Further Extensions59:44
Concluding Remarks01:02:17
Thank you01:02:48