| # | Date | Topic of Paper (Sellect from below or: Collection of Local ratio papers) | Speaker |
|---|---|---|---|
| 1 | 4/3 | Introduction - Optimization and Approximation
(Vazirani's notes: Chapters I+II pages 3-15 (PDF)) (Compendium intro) (Slides) | Alex Levin |
| 2 | 11/3 | Intro to linear programming
( CLRS book,
at technion library)
...and its use in approximation algorithms (Vazirani's notes: Chapters 11 pages 59-62 (PDF)) (Slides) | Michael Krel |
| 3 | 18/3 | The Primal Dual Method for Approximation Algorithms (Vazirani's notes: Chapters 12-13 pages 63-72 (PDF)) (Page) (Slides) | Tamir Carmeli |
| Teacher | 25/3 | R. Bar-Yehuda. One for the price of two (paper) (Slides) (Movie) | Reuven Bar-Yehuda |
| 4 | 8/4 | Bar-Yehuda, R., Using Homogeneous Weights for Approximating the Partial Cover Problem, Journal of Algorithm, 39, 137-144, 2001. ( PDF ) (Slides) | Evyatar Lavian -2 |
| 5 | 8/4 | On Approximating a Vertex Cover for Planar Graphs | Anna Livshits -2+1 |
| 6 | 15/4 | R. Bar-Yehuda and D. Rawitz. Efficient Algorithms for Integer Programs with Two Variables per Constraint (Paper) | Nadav Jonas |
| 7 | 15/4 | Part 2 | Daniel Rembiszewski |
| 8 | 22/4 | R. Bar-Yehuda I. Feldman and D. Rawitz, Improved Approximation Algorithm for Convex Recoloring of Trees, WAOA 2005, Theory of Computing Systems, 43, 3-18, 2008. ( PDF) (Slides) (Summary page) | Inbal Sertshuk |
| 9 | 22/4 | Local Ratio for Vertex Cover | Rafael Alan Goldfarb |
| 10 | 29/4 | A. Bar-Noy, R. Bar-Yehuda, A. Freund, S. Naor, and B. Schieber. A Unified Approach to Approximating Resource Allocation and Scheduling | Albagli Sivan* |
| 11 | 29/4 | Part B | Tomer London |
| 12 | 6/5 | Vertex Feedback Set Approximations | Ami Paz |
| 13 | 6/5 | A General Approximation Technique for Constrained Forest Problems | Alor Yotam* |
| ----- | 13/5 | Student day: NO CLASS | NO CLASS |
| ----- | 20/5 | Shavuo'ot gesher: NO CLASS | NO CLASS |
| Teacher | 27/5 | Bandwidth Allocation in Networks with Multiple Interferences | Reuven Bar-Yehuda |
| 14 | 3/6 | Exploiting Locality: Approximating Sorting Buffers | Or Kaduri -1 |
| Teacher | 3/6 | Hall theorem via local ratio (txt) | Reuven Bar-Yehuda |
| 15 | 10/6 | Data Migration to Minimize Average Completion Time | Shahar Chen* |
| Teacher LAST | 17/6 | Fractional local ratio | Reuven Bar-Yehuda |
This page has been visited
times since the last reset.