Reuven Bar-Yehuda

My lecturse on YouTube.
Seminar course on "Local-Ratio/Primal Dual" .

Reuven Bar-Yehuda
Computer Science Department
Technion IIT
Haifa 32000 Israel

e-mail: reuven AT cs.technion.ac.il
Phone (Office) +972-4-8294332
Fax +972-4-829-3900
My academic father, Shimon Even died on May 1st, 2004

Welcome to my home-page. I am interested in combinatorial algorithms. This includes Approximation Algorithms , Computational Geometry and Applications , Theoretical Aspects of Communications , Practical Aspects of VLSI , and Others .

Download papers: PDF .

Download papers: PS .

Download slides: SLIDES .

Seminar course on "Local-Ratio/Primal Dual" .

My ex-wife "Approximation Algorithms for Combinatorial Optimization Problems" is back. I am putting more commitment into our relationship ( See how much) I am trying to understand her more using the "Local-Ratio" technique:

The Local-Ratio Technique
The Local-Ratio Theorem: If a feasible solution is r-approximation w.r.t a pair of weight functions W1 and W2 then it is also an r-approximation w.r.t W1+W2 ( Why? ).
This yields a unified approach for many fundamental optimization problems e.g.:
Applications to some optimization algorithms (r = 1):
( MST) Minimum Spanning Tree (Kruskal)
( SHORTEST-PATH) s-t Shortest Path (Dijkstra)
(LONGEST-PATH) s-t DAG Longest Path (Can be done with dynamic programming)
(INTERVAL-IS) Independents-Set in Interval Grapths Usually done with dynamic programming)
(LONG-SEQ) Longest (weighted) monotone subsequence (Can be done with dynamic programming)
( MIN_CUT) Minimum Capacity s,t Cut (e.g. Ford, Dinitz)
Applications to some 2-Approximation algorithms: (r = 2)
( VC) Minimum Vertex Cover (Bar-Yehuda and Even)
( FVS) Vertex Feedback Set (Becker and Geiger)
( GSF) Generalized Steiner Forest (Williamson, Goemans, Mihail, and Vazirani)
( Min 2SAT) Minimum Two-Satisfiability (Gusfield and Pitt)
( 2VIP) Two Variable Integer Programming (Bar-Yehuda and Rawitz)
( PVC) Partial Vertex Cover (Bar-Yehuda)
( GVC) Generalized Vertex Cover (Bar-Yehuda and Rawitz)
Applications to some other Approximations:
( SC) Minimum Set Cover (Bar-Yehuda and Even)
( PSC) Partial Set Cover (Bar-Yehuda)
( MSP) Maximum Set Packing (Arkin and Hasin)

Curriculum Vitae (PS) (PDF) (html with links to papers)



Slides: (Partial Cover)Soda99.ps.gz
Local_Ratio_With_LP.ps.gz
(2VIP)ESA99.ps.gz
(Resoruce Allocation)STOC2000.ppt
(Geometric TSP (winxp))ESA2003.ppt
(Geometric TSP) (WIN2000)ESA2003a.ppt


TECH-WEB calendar

Call me!