( Grades from winter 10)
Course info page
The seminar will focus on two approaches that were used to construct many
approximation algorithms during the last two decades: the primal-dual
schema and the local-ratio technique (though, rounding may come up as
well).
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.
This page has been visited
For registration please e-mail:
to: reuven@cs.technion.ac.il
Subject: seminar 236813
body: your info, in the format:
Name+FamilyName+email+ID+Phone#+AverageGrade
e.g. Reuven Bar-Yehuda reuven@cs 123456789 04-8294332 87
Details
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
(Sellect from below or: Collection of Local ratio papers)
Speaker
1
15/10/09
Introduction - Optimization and Approximation
(Vazirani's notes: Chapters I+II pages 3-15 (PS))
(Compendium intro)
(Slides)
Alexander Nus -2
2
22/10/09
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)
Tal Weiss
3
29/10/09
The Primal Dual Method for Approximation Algorithms
(Vazirani's notes: Chapters 12-13 pages 63-72 (PS))
(slides)
Benjamin Klein
Teacher
5/11/09
R. Bar-Yehuda. One for the price of two
(paper)
(Slides)
(Movie)
Reuven Bar-Yehuda
4
12/11/09
Bar-Yehuda, R., Using Homogeneous Weights for Approximating the Partial Cover
Problem, Journal of Algorithm, 39, 137-144, 2001.
( PDF )
(Slides)
Raeda Zoabi
5
19/11/09
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)
Netanel Raviv
Teacher
26/11/09
A. Bar-Noy, R. Bar-Yehuda, A. Freund, S. Naor, and B. Schieber.
A Unified Approach to Approximating Resource Allocation and
Scheduling
(Slides )
Reuven Bar-Yehuda
6
3/12/09
Reuven Bar-Yehuda and Jonathan Laserson
Exploiting Locality: Approximating Sorting Buffers, WAOA 2005,
( PDF )
(Slides1)
(Slides2)
Eyal Kibbar*
----- 10/12/09 NO CLASS NO CLASS
----- 17/12/09 HANUKA NO CLASS
Teacher
24/12/09
LP Rounding using Fractional Local Ratio
(Slides)
Reuven Bar-Yehuda
7
31/12/09 FVS via Primal Dulal
(Slides)
Lior Teller
8 7/1/10
The Minimum Substring Cover Problem
By Danny Hermelin, Dror Rawitz,
Romeo Rizzi, and Stephane Vialette
Published in Information and Computation journal, Volume 206
(Slides)
Keren Lenz*
9
NEXT
14/1/10 Node Deletion Daniel Dorr*
-- 21/1/10
Hall theorem via local ratio
(txt)
Reuven Bar-Yehuda
Links
Books
times since the last reset.