1. Introduction - Optimization and Approximation
    Vazirani's notes: Chapters I+II pages 3-15
    ( PDF)
    Pierluigi Crescenzi, Viggo Kann and Magnus Halldorsson
    A compendium of NP optimization problems
    (LINK )
  2. Intro to linear programming
    At CS Technion library: ( CLRS book)
    ...and its use in approximation algorithms
    Vazirani's notes: Chapters 10-11 pages 52-62
    ( PDF)
  3. The Primal Dual Method for Approximation Algorithms, Set cover, see:
    Vazirani's notes: Chapter 13 pages 69-72
    (PDF)
  4. Bar-Yehuda, R., Using Homogeneous Weights for Approximating the Partial Cover
    Problem, Journal of Algorithm, 39, 137-144, 2001.
    ( PDF )
  5. 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. do only chapters 1-3.2
    ( PDF )
    ( PDF )
  6. Reuven Bar-Yehuda, Danny Hermelin and Dror Rawitz.
    Minimum vertex cover in rectangle graphs.
    Computational Geometry: Theory and Applications.
    ( PDF )
  7. 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 )
    ( PS )
  8. Bar-Yehuda, R. and D. Rawitz. Efficient Algorithms for Integer Programs with
    Two Variables per Constraint Algorithmica 29(4):595-609, 2001.
    ( PDF )
    do only chapters 1-3
  9. 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
    ( PDF )
  10. Bar-Yehuda R. and D. Rawitz.
    A note on multicovering with disks. Computational Geometry,
    Theory and Applications 46(3):394-399, 2013
    ( PDF )
  11. Julian Mestre, Adaptive Local Ratio. SODA 2008 (received the Best Student Paper Award)
    (PDF)
    ( PDF2 )
  12. M. X. Goemans and D. P. Williamson.
    A General Approximation Technique for Constrained Forest Problems
    (PDF)
  13. 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 t
    ( PDF )
    ***comment: do only chapters 1-4
  14. Reuven Bar-Yehuda, Keren Censor-Hillel, Gregory Schwartzman:
    A Distributed (2 + epsilon )-Approximation for Vertex Cover in O(log Delta / epsilon log log Delta) Rounds.
    J. ACM 64(3): 23:1-23:11 (2017)
    ( PDF )
    ***comment: do only chapters 1-3
  15. F. A. Chudak, M. X. Goemans, D. S. Hochbaum, and D. P. Williamson.
    A primal-dual interpretation of recent 2-approximation
    algorithms for the feedback vertex set problem in undirected graphs.
    (PDF)
    (PS)
  16. 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.
    ***comment: do only chapters 1-4
    ( PDF )
  17. Reuven Cohen Liran Katzir Danny Raz
    An Efficient Approximation for the Generalized assignment Problem, IPL 2006
    ( PDF )
  18. Daniel Lokshtanov, Pranabendu Misra, Joydeep Mukherjee, Fahad Panolan, Geevarghese Philip, Saket Saurabh,
    2-Approximating Feedback Vertex Set in Tournaments
    ( PDF )
  19. Refael Hassin and Asaf Levin,
    The minimum generalized vertex cover problem,
    Journal ACM Transactions on Algorithms (TALG) TALG Homepage archive
    Volume 2 Issue 1, January 2006 Pages 66-78
    ( PDF )
  20. Reuven Bar-Yehuda and Jonathan Laserson
    Exploiting Locality: Approximating Sorting Buffers,
    WAOA 2005,
    ( PDF )
  21. Reuven Bar-Yehuda, Michael Beder, Yuval Cohen, and Dror Rawitz.
    Resource allocation in bounded degree trees.
    Algorithmica, 54(1):89-106, 2009.
    ( PDF )
  22. 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 )
  23. 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
    Other papers that use the Local Ratio technique:
    ( PDF )
  24. Bar-Yehuda, R. and D. Rawitz. Local ratio with negative weights,
    Operations Research Letters, Vol 32, Issue 6, Pages 540-546 (November 2004).
    ( PS )
    ( LINK )
  25. 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),
    ( PDF )
    ( LINK )
    Vol. 40 (2004), pp. 293-304.
  26. 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.
    ( PDF )
  27. 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.
    ( LINK )
    ( PS )
  28. 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
  29. 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
    ( PDF )
  30. 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
  31. Shai Gutner,
    Elementary approximation algorithms for prize collecting Steiner tree problems,
    IPL, 107, 1, 30 , 39-44 , 2008
    ( PDF )
  32. Zhenbo Wang., Zhenhua Cui
    Combination of parallel machine scheduling and vertex cover
    Theoretical Computer Science 460 (2012) 10-15
    ( PDF2 )
  33. 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 )
  34. Marie-France Sagot b,c, Leen Stougied,e,
    Vicente Acu-nab, Flavio Chierichetti, Vincent Lacroixb, Alberto Marchetti-Spaccamelaa,
    Modes and cuts in metabolic networks: Complexity and algorithms
    ( PDF )
  35. Julia'n Mestre, Jose' Verschae,
    A 4-approximation for scheduling on a single machine with general cost function
    ( PDF )
  36. Yaping Zhang, Yishuo Shi, Zhao Zhang
    Approximation algorithm for the minimum weight connected k-subgraph cover problem
    Theoretical Computer Science 05/2014
    ( PDF )
  37. Samuel Fiorini, Gwenaël Joret, Oliver Schaudt,
    Improved approximation algorithms for hitting 3-vertex paths,
    ( LINK )
    ( PDF )
  38. R. Bar-Yehuda. One for the Price of Two: a Unified Approach for Approximating Covering Problems
    Algorithmica June 2000, Volume 27, Issue 2, pp 131-144
    (paper)
    (Slides)
    (Movie)