Reuven BarYehuda
My lecturse on YouTube.
Seminar course on "LocalRatio/Primal Dual" .

Reuven BarYehuda 
Computer Science Department 
Technion IIT 
Haifa 32000 Israel 

email: reuven AT cs.technion.ac.il 
Phone (Office) +97248294332 
Phone (Home) +97248226181 
Fax +97248293900 


Welcome to my homepage. 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 "LocalRatio/Primal Dual" .
My exwife "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 "LocalRatio" technique:
The LocalRatio Technique
The LocalRatio Theorem:
If a feasible solution is
rapproximation w.r.t a pair of weight functions W1 and W2 then it
is also an rapproximation 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)
( SHORTESTPATH) st Shortest Path
(Dijkstra)
(LONGESTPATH) st DAG Longest Path
(Can be done with dynamic programming)
(INTERVALIS) IndependentsSet in Interval Grapths
Usually done with dynamic programming)
(LONGSEQ) Longest (weighted) monotone subsequence
(Can be done with dynamic programming)
( MIN_CUT) Minimum Capacity s,t Cut
(e.g. Ford, Dinitz)
Applications to some 2Approximation algorithms: (r = 2)
( VC) Minimum Vertex Cover
(BarYehuda and Even)
( FVS) Vertex Feedback Set
(Becker and Geiger)
( GSF) Generalized Steiner Forest
(Williamson, Goemans, Mihail, and Vazirani)
( Min 2SAT) Minimum TwoSatisfiability
(Gusfield and Pitt)
( 2VIP) Two Variable Integer Programming
(BarYehuda and Rawitz)
( PVC) Partial Vertex Cover
(BarYehuda)
( GVC) Generalized Vertex Cover
(BarYehuda and Rawitz)
Applications to some other Approximations:
( SC) Minimum Set Cover
(BarYehuda and Even)
( PSC) Partial Set Cover
(BarYehuda)
( 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
TECHWEB
calendar