LP/IP problems with LR/PD techniques
We will start with a short introduction to the field of approximation algorithms, and then an overview of both methods will be presented.
The studies that will be presented during the semester deal with a variety of problems including several fundamental problems, such as the Steiner forest problem, the metric uncapacitated facility location problem, and the feedback vertex set problem.
| Instructor: | Reuven Bar-Yehuda |
| Time: | Thr. 14:30-17:30 (average of 2 hours a week) |
| Place: | Taub 4 (at Floor 1) |
| # | Date | Topic of Paper | Speaker |
|---|---|---|---|
| 1 | Thr 14:30
3/11/05 | Introduction - Optimization and Approximation
(Vazirani's notes: Chapters I+II pages 3-15 (PS)) (Compendium intro) (Slides) | ??? |
| 2+3 | Thr 14:30
??? | Intro to linear programming
( CLRS book,
at technion library)
...and its use in approximation algorithms (Vazirani's notes: Chapters 11 pages 59-62 (PS)) (Slides) | Javier Turek & Eran Triester |
| 4 | Thr 14:30
17/11/05 | The Primal Dual Method for Approximation Algorithms (Vazirani's notes: Chapters 12-13 pages 63-72 (PS)) (slides) | Dan Raviv |
| - | Thr 14:30
24/11/05 | R. Bar-Yehuda. One for the price of two (paper) (Slides) | Reuven Bar-Yehuda |
| 5 | Thr 14:30
1/12/05 | R. Bar-Yehuda. Using Homogenous Weights for Approximating the Partial Cover Problem (Paper) (Slides ) | Maria Artishchev-Zapolotsky |
| 6 | Thr 15:30
1/12/05 | S. Guha, R. Hassin S. Khuller and E. Or Capacitated Vertex Covering with Applications , (Slides) | Michael Beder |
| 7+8 | Thr 14:30
8/12/05 | R. Bar-Yehuda and D. Rawitz. Efficient Algorithms for Integer Programs with Two Variables per Constraint (Paper) (Slides) | Shaphir Evgeny and Alex Landau |
| 9+10 | Thr 14:30
15/12/05 |
| Dan Baum & Ilan Gronau |
| -- | Thr 14:30
22/12/05 | Fractional Local Ratio (Slides ) | Reuven Bar-Yehuda |
| 11 | Thr ~16:00
22/12/05 | T. Fujito. A Unified Approximation Algorithm for Node-Deletion Problems (Slides ) | Adi Mano |
| 12+13 | Thr 14:30
29/12/05 | M. X. Goemans and D. P. Williamson. A General Approximation Technique for Constrained Forest Problems (Paper) (Slides) | Sergey Novikov and Roostam Tiger |
| 14+15 | Thr 14:30
5/1/05 | Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems (1999) Kamal Jain, Vijay V. Vaziran (Slides) | Oleg Rokhlenko & Janna Burman |
| 16+17 | Thr 14:30
12/1/05 |
A. Bar-Noy, R. Bar-Yehuda, A. Freund, S. Naor, and B. Schieber.
A Unified Approach to Approximating Resource Allocation and
Scheduling
(Slides) | Michal Segalov & Noga Tal |
| -- | 16:30
12/1/05 | Resource allocation (again) (Slides) (full version slides) | Reuven Bar-Yehuda |
| 18 | Thr 14:30
19/1/05 | Approximation for Buffer Sorting (Paper) | Yochay Tzur |
| 19 | ~15:30
19/1/05 | Bar-Yehuda R., M. M. Halldorsson, J. Naor, H. Shachnai and I. Shapira, Scheduling Split Intervals, Thirteenth ACM-SIAM Symposium on Discrete Algorithms (SODA), January 6-8, 2002 San Francisco. ( Journal version ) ( New developments ) (slides) (Slides) | Gadi Aleksandrowicz |
| -- | 26/1/05 | -- | -- |
| 20 NEXT | Thr 14:30
2/2/06 | Bar-Yehuda, R. and S.~Even. A local-ratio theorem for approximating the weighted vertex cover problem. {\em Annals of Discrete Mathematics}, 25:27--46, 1985. (paper) (Slides) | Yair Tshop |
| 21 NEXT | ~15:30
2/2/06 | Akcoglu, J. Aspnes, B. DasGupta, and M. Kao. Opportunity Cost Algorithms for Combinatorial Auctions (Slides) | Oren K. |
| 22 NEXT | ~16:30
2/2/06 | R. Bar-Yehuda I. Feldman and D. Rawitz, Improved Approximation Algorithm for Convex Recoloring of Trees, Exploiting Locality: Approximating Sorting Buffers, WAOA 2005, ( PDF ) | Michael Ryabtsev |
This page has been visited
times since the last reset.