Local Ratio papers by Reuven Bar-Yehuda:
---------------------------------------
A subset of cv file ( HTML ) 
 
a1. Bar-Yehuda, R. and S. Even. A linear time approximation algorithm for the weighted vertex cover problem.  
   Journal of Algorithms, 2:198--203, 1981. 
   ( PDF )   (the first Primal Dual schema)

a2. Bar-Yehuda, R. and S. Even. A Local-Ratio Theorem for Approximating the Weighted 
   Vertex Cover problem. Annals of Discrete Mathematics, 25:27--46, 1985. 
   ( PDF )    (the first Local ratio)

a3. Bar-Yehuda, R. and S. Even. On Approximating a Vertex Cover for Planar Graphs, 
   Proceeding of the Fourteenth Annual ACM Symposium on Theory of Computing (STOC), 
   San Francisco, California, May 5-7, 1982, pp. 303-309.
   ( PDF )

a4. Bar-Yehuda, R., D. Geiger, J. Naor, and R. Roth. Approximation Algorithms for the 
   Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian 
   Inference, SIAM Journal on Computing, 27, 4 1998, 942-959. 
   ( PDF )

a5. Bar-Yehuda, R., One for the Price of Two: A Unified Approach for Approximating Covering 
   Problems, Algorithmica 27(2), 2000, 131-144.
   ( PDF )

a6. Bar-Yehuda, R. and D. Rawitz. Efficient Algorithms for Integer Programs with 
   Two Variables per Constraint Algorithmica 29(4):595-609, 2001.
   ( PDF )

a7. Bar-Yehuda, R., Using Homogeneous Weights for Approximating the Partial Cover 
   Problem, Journal of Algorithm, 39, 137-144, 2001.
   ( PDF )

a8. Bar-Noy A., Bar-Yehuda, R., Freund A., Naor J., and B. Schieber, A unified approach to 
   approximating resource allocation and scheduling, Journal of the ACM, Vol. 48, No.5 (2001), 
   pp. 1069-1090.
   ( PDF )
   ( PDF )

a9. Bar-Yehuda, R., and D. Rawitz, Approximating Element-Weighted Vertex Deletion Problems for 
   the Complete k-partite Property, Journal of Algorithms, 42(1):20-40, 2002.
   ( LINK )

a10.Bar-Yehuda, R. and D. Rawitz. Local ratio with negative weights, 
   Operations Research Letters, Vol 32, Issue 6, Pages 540-546 (November 2004).
   ( LINK )

a11.Bar-Yehuda, R., and Z. Kehat, Approximating the Dense Set-Cover Problem Journal of Computer 
   and System Sciences Volume 69, Issue 4 , December 2004, Pages 547-561.
   
a12.Bar-Yehuda, R., D. Rawitz, On the Equivalence Between the Primal-Dual Schema and the Local-Ratio 
   Technique, APPROX 2001, Berkeley, California, USA, 18-20 August 2001.
   Submitted to Siam J. on Disc. Math.
   ( PDF )
   
a13.Bar-Yehuda R., M. M. Halldorsson, J. Naor, H. Shachnai and I. Shapira, Scheduling Split Intervals, 
   13th ACM-SIAM Symposium on Discrete Algorithms (SODA), January 6-8, 2002 San Francisco. Accepted
   for publication, SIAM J. Computing.
   ( PDF )

a14.Bar-Yehuda, R., K. Bendel, A. Freund, and D. Rawitz,
   Local ratio: A unified framework for approxmation algrithms in memoriam: Shimon Even 1935-2004
   J ACM Comput. Surv. 36, 4, 422-463, 2004.
   ( PDF )
   ( LINK )
 
a15.Bar-Yehuda, R., D. Rawitz, 
   Using fractional primal-dual to schedule split intervals with demands
   (Fracional Primal Dual Based on Fractionl Local Ratio)
   Submitted to ICALP05 and Mathematical Programming.
   ( PDF )
 
a16.Reuven Bar-Yehuda and Jonathan Laserson
   Exploiting Locality: Approximating Sorting Buffers,
   WAOA 2005,
   ( PDF )
 
a17.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.
http://www.cs.technion.ac.il/~reuven/PDF/convex.pdf
   ( PS )

a18.Bar-Yehuda R. and I. Yavneh,
   A Factor-Two Approximation Algorithm for Two-Dimensional Phase-Unwrapping,
   submitted to J. Graph Algorithms and Applications,
   ( PDF )

a19.Reuven Bar-Yehuda, Michael Beder, Yuval Cohen, and Dror Rawitz.
	Resource allocation in bounded degree trees.
	Algorithmica, 54(1):89-106, 2009.
   ( LINK )
   ( PDF )

a20.A chapter in the Memorial book for Shimon Even
   ( PS )

a21.R. Bar-Yehuda G. Flysher Julian Mestre and D. Rawitz,
Approximation of Partial Capacitated Vertex Cover
SIAM J. Discrete Math. Volume 24, Issue 4, pp. 1441-1469 (2010)
   ( PDF )
   ( LINK )


a22. Amzallag, D.; Bar-Yehuda, R.; Raz, D.; Scalosub, G.,
   "Cell Selection in 4G Cellular Networks,"
   IEEE Transactions on Mobile Computing, 
   vol.12, no.7, pp.1443,1455, July 2013
   ( PDF )

a23.Bar-Yehuda R, D. Hermelin and D. Rawitz,
   An Extension of the Nemhauser-Trotter Theorem to Generalized Vertex Cover with Applications.
    735 SIAM J. Discrete Math. Volume 24, Issue 1, pp. 287-300, 2010.
   ( PDF )

a24.  Reuven Bar-Yehuda, Danny Hermelin and Dror Rawitz.
	Minimum vertex cover in rectangle graphs.
	Computational Geometry: Theory and Applications.
   ( PDF )

Other papers that use the Local Ratio technique:
-----------------------------------------------------

b1. Liane Lewin-Eytan, Joseph Naor and Ariel Orda,
   Admission control in networks with advance reservations,
   Algorithmica, Special Issue on
   approximation and online algorithms (by invitation),
   ( LINK )
   Vol. 40 (2004), pp. 293-304.

b2. Joseph Naor, Hadas Shachnai and Tami Tamir,
   Real-time scheduling with a budget,
   Proceedings of the
   30th International Colloquium on Automata,Languages, and Programming
   (ICALP), Eindhoven, The Netherlands (2003), pp. 1123-1137.
   ( PS )

b3. Vineet Bafna, Piotr Berman, Toshihiro Fujito,
   A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem,
   SIAM Journal on Discrete Mathematics Volume 12, Number 3 pp. 289-297
   ( LINK )

b4. Mao-cheng Cai, Xiaotie Deng, Wenan Zang:
   An Approximation Algorithm for Feedback Vertex Sets in Tournaments.
   SIAM Journal on Computing, Vol. 30 (2000), 1993-2007.
   ( LINK )

b5. Toshihiro Fujito
   A Unified Local Ratio Approximation of Node-Deletion Problems (Extended Abstract)
   Lecture Notes In Computer Science; Vol. 1136 archive
   Proceedings of the Fourth Annual European Symposium on Algorithms 
   Pages: 167 - 178  Year of Publication: 1996
   ( LINK )
   ( LINK )

b6. Randeep Bhatia, Julia Chuzhoy, Ari Freund, and Joseph Naor,
   Algorithmic aspects of bandwidth trading, Proceedings of the
   30th International Colloquium on Automata,Languages, and Programming
   (ICALP), Eindhoven, The Netherlands (2003), pp. 751-766.
   ( PS )

b8. Amotz Bar-Noy, Sudipto Guha, Yoav Katz,
   Joseph Naor, Hadas Shachnai and Baruch Schieber,
   Throughput maximization of real-time scheduling with batching,
   Proceedings of the 13th Annual ACM-SIAM Symposium
   on Discrete Algorithms (SODA), San Francisco, California (2002), pp. 742-751.
   ( PS )

b9. Rajiv Gandhi, Samir Khuller and Aravind Srinivasan.
   Approximation Algorithms for Partial Covering Problems.
   ICALP 2001. J. of Algorithms Vol 53(1): 55--84 (2004). 
   ( PS )

b10.Zhi-Zhong Chen Tao Jiang, Guohui Lin, Jianjun Wen, Dong Xu, Jinbo Xu, Ying Xu, 
   Approximation algorithms for NMR spectral peak assignment . 
   Theoretical Computer Science. (Joint with T. Jiang, G.-H. Lin, ...)
   ( PDF )

   A new version with better results was presented at WABI2002. 
   ( PDF )

b11.Okun and Amnon Barak, 
   A new approach for approximating node deletion problems,
   J Inf. Process. Lett. 231-236, 003 
   ( LINK )
   Elsevier North-Holland, Inc.

b12.M. Krivelevich, R.Nathaniel and B. Sudakov, 
   Approximating coloring and maximum independent set in 3-uniform hypergraphs,
   J. of Algorithm 41 (2001), 99-113. 
   An extended abstract appeared in: Proc. of the 12th Annual ACM-SIAM SODA, ACM Press (2001), 327-328. 
   ( PDF )
   ( PDF )
   ( PDF )

b13.Madhav V. Marathe and Heinz Breu and Harry B.and S. S. Ravi and Daniel J. Rosenkrantz,
   Simple Heuristics for Unit Disk Graphs, Networks,  25,   59--68,  1995,
   ( PDF )
   
b14.Karhan Akcoglu, James Aspnes, Bhaskar DasGupta, Ming-Yang Kao,
   Opportunity Cost Algorithms for Combinatorial Auctions CoRR cs.CE/0010031: (2000)
   ( PDF )
   
b15.Jens S. Kohrt, Kirk Pruhs,
   A Constant Approximation Algorithm for Sorting Buffers. LATIN 2004: 193-202
   ( PDF )
   www.springerlink.com/index/FQBC84923GVEUHLR.pdf"> PDF )
   
b16.A. Freund and D. Rawitz,
   Combinatorial Interpretations of Dual Fitting and Primal Fitting,
   Proc. 1st Workshop on on Approximation and Online Algorithms (WAOA03), 2003.
   To appear in LNCS (C) Springer-Verlag, 2003.
   ( PS )
   www.springerlink.com/index/1DN6E1LEW7ETKYEN.pdf"> PDF )

b17.Yong Zhang, Hong Zhu,
   An Approximation Algorithm for Weighted Weak Vertex Cover Problem in Undirected Graphs.
   COCOON 2004: 143-150
   ( PDF )

b18.Reuven Cohen, Liran Katzir, Danny Raz,
   Scheduling Algorithms for a Cache Pre-Filling Content Distribution Network. INFOCOM 2002
   ( PDF )
   ( PDF ) Also a thesis under R. Cohen Supervision

b19.Rami Cohen, Dror Rawitz, Danny Raz,
   Time Dependent Multi Scheduling of Multicast,
   In 12th Annual European Symposium on Algorithms (ESA 04),
   pages 216-227, September 2004, Bergen, Norway
   ( PDF ) Also a thesis under D. Raz Supervision
   
b20. Shlomo Moran and Sagi Snir,
    Convex Recoloring of Strings and Trees
   ( PDF )
   ( LINK ) Also a thesis under S. Moran Supervision

b21.Anna Moss and Dan Geiger,
   Optimization of Pearl's method of conditioning and greedy-like approximation algorithms
   for the vertex feedback set problem, Becker A., Geiger D.,
   Artificial Intelligence 1996; 83:167—188  
   ( PS ) Using LR dtating it.
 
   Optimization of Bayesian Inference and Approximation Algorithms for the Weighted Vertex Feedback Set Problem ,
   M.Sc. Thesis 1995
   ( PDF ) A thesis under D. Geiger Supervision

b22.Allan Borodin, David Cashman and Avner Magen,
   How well can Primal-Dual and Local-Ratio algorithms perform,
   ICALP July, 2005.
   ( PS ) Also a thesis under A. Borodin and A. Magen Supervision


b23. Udo Adamy1, Thomas Erlebach2, Dieter Mitsche1, Ingo Schurr1,
    Bettina Speckmann3  and Emo Welzl1,
    Off-line Admission Control for Advance Reservations in Star Networks
    ( LINK )

b24.  Approximation Complexity of Optimization Problems: Structural Foundations and Steiner Tree Problems,
     Dissertation zur Erlangung des Doktorgrades (Dr. rer. nat.)
     der Mathematisch-Naturwissenschaftlichen FakultÄat
     der Rheinischen Friedrich-Wilhelms-UniversitÄat Bonn vorgelegt von Mathias Hauptmann aus Oldenburg Bonn, April 2004
    ( PDF Thesis)

b25. G. Calinescu and A. Dumitrescu and J. Pach, Reconfigurations in graphs and grids,
	Proc. LATIN '06 (Latin American Theoretical INformatics conference),
	Lecture Notes in Computer Science 3887, Springer, 2006, 262-273
    ( PDF )

b26. G. Even, J. Feldman, G. Kortsarz and Z. Nutov, 
	A 3/2-approximation for augmenting a connected graph into a two-connected graph, 
	The journal version of this paper is divided into two parts. 
    ( PS-first )
	Preliminary version in Approx 2001, pages 90--101 

b27. Approximation Complexity of Optimization Problems:
	Structural Foundations and Steiner Tree Problems
	Dissertation zur Erlangung des Doktorgrades (Dr. rer. nat.)
	Der Mathematisch-Naturwissenschaftlichen Fakult?at
	Der Rheinischen Friedrich-Wilhelms-Universit?at Bonn
	vorgelegt von Mathias Hauptmann aus Oldenburg Bonn, April 2004
	( PDF Thesis)

b28. Ari Freund and Dror Rawitz. 
	Combinatorial interpretations of dual fitting and primal fitting. 
	Extended abstract appeared in 1st WAOA, LNCS 2909:137-150, 2003. 
	( PS )

b29. A constant approximation algorithm for sorting buffers 
Jens S. Kohrt and Kirk Pruhs.
In Proceedings of the Sixth Latin American Symposium (LATIN 2004), volume 2976 of Lecture Notes in Computer Science, pages 193-202. Springer-Verlag, 2004. 

b30. Julian Mestre,
	Adaptive Local Ratio.  SODA 2008 (received the Best Student Paper Award)
    (PDF)
    ( PDF2 ) 

b31. Reuven Cohen Liran Katzir Danny Raz
An Efficient Approximation for the Generalized  assignment Problem, IPL 2006
    ( PDF ) 

b32. Shai Gutner,
Elementary approximation algorithms for prize collecting Steiner tree problems,
IPL, 107, 1, 30 , 39-44  , 2008
   ( PDF )

b33. Zhenbo Wang., Zhenhua Cui
Combination of parallel machine scheduling and vertex cover
Theoretical Computer Science 460 (2012) 10-15
    ( PDF2 ) 


b35. Christos Koufogiannakis, Neal E. Young
Distributed Fractional Packing and Maximum Weighted b-Matching via Tail-Recursive Duality
Distributed Computing Lecture Notes in Computer ScienceVolume 5805, 2009, pp 221-238 
    ( PDF2 ) 


b35. Marie-France Sagot b,c, Leen Stougied,e,
Vicente Acu-nab,c, Flavio Chierichetti a, Vincent Lacroixb,c,f, Alberto Marchetti-Spaccamelaa,
Modes and cuts in metabolic networks: Complexity and algorithms
   ( LINK )

b36. Julia'n Mestre, Jose' Verschae, A 4-approximation for scheduling on a single machine with general cost function
   ( LINK )