The Primal-Dual approach for Online Algorithms

Published on 2012-10-025265 Views

Nikhil Bansal

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

ALGO 2012 - Ljubljana

Related categories

Presentation

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