next up previous
Next: Book Chapters Up: Refereed papers in professional Previous: Refereed papers in professional


  1. 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
  2. Bar-Yehuda, R. and U. Vishkin. Complexity of finding k-path-free dominating sets in graphs. Information Processing Letters, 14(5):228-232, 1982.
  3. Bar-Yehuda, R. and S. Moran. On approximation problems related to the independent set and vertex cover problems. Discrete Applied Mathematics, 9:1-10, 1984.
  4. 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
  5. Bar-Yehuda, R. and S. Kutten. Fault tolerant distributed majority commitment. Journal of Algorithms, 9(4):568-582, December 1988.
  6. Bar-Yehuda, R., J. A. Feldman, R. Y. Pinter, and S. Wimer. Depth first search and dynamic programming algorithms for efficient CMOS cell generation. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 8(7), 1989. Link
  7. Bar-Yehuda, R., O. Goldreich, and A. Itai. Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detection. Distributed Computing, 5(2):67-72, 1991. PDF
  8. Bar-Yehuda, R., O. Goldreich, and A. Itai. On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization. Journal of Computer and System Sciences, 45:104-126, 1992. PDF
  9. Bar-Yehuda, R., T. Etzion, and S. Moran. Rotating-table games and derivatives of words. Theoretical Computer Science, 108:311-329, 1993. Link
  10. Bar-Yehuda, R. and S. Fogel. Variations on ray shooting. Algorithmica, 11:133-145, 1994.
  11. Bar-Yehuda, R. and T. Etzion. Connections between two cycles - A new design of dense processor interconnection networks. Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science, 38:29-43, 1992.
  12. Bar-Yehuda, R., B. Chor, E. Kushilevitz, and A. Orlitsky. Privacy, additional information, and communication. IEEE Transactions on Information Theory, 39(6):1930-1943, 1993.
  13. Bar-Yehuda, R., A. Israeli, and A. Itai. Multiple communication in multi-hop radio networks. SIAM Journal on Computing, 22(4):875-887, August 1993. PDF
  14. Bar-Yehuda, R. and B. Chazelle. Triangulating disjoint Jordan chains. Int. J. of Computational Geometry & Appl., 4(4):475-481, 1994. PDF
  15. Bar-Yehuda, R. and E. Ben-Hanoch. A linear time algorithm for covering simple polygons with similar rectangles. Int. J. of Computational Geometry & Appl., 6(1):79-102, 1996. PDF
  16. Bar-Yehuda, R. C. Gotsman. Time/space tradeoffs for polygon mesh rendering. ACM Trans. on Graphics, 15(2):141-152, 1996. PDF
  17. Cohen, S., G. Elber, and R. Bar-Yehuda. Matching of freeform curves. Computer Aided Design, 29(5):369-378, 1997. PDF
  18. 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):942-959, 1998. PDF Download from SIAM electronic publication
  19. Bar-Yehuda, R. and S. Fogel. Partitioning a sequence into few monotone subsequences. Acta Informatica, 35:421-440, 1998. Postscript BibTeX+Abstract
  20. Becker, A., R. Bar-Yehuda, and D. Geiger. Randomized Algorithms for the Loop Cutset Problem, Journal Artificial Intelligence Research 12:219-234, 2000. Download from JAIR electronic publication
  21. Bar-Yehuda, R., One for the Price of Two: A Unified Approach for Approximating Covering Problems, Algorithmica 27(2), 2000:131-144, 2000. PDF
  22. Bar-Yehuda, R. and D. Rawitz. Efficient Algorithms for Integer Programs with Two Variables per Constraint, Algorithmica 29(4):595-609, 2001. PDF
  23. Bar-Yehuda, R., Using Homogeneous Weights for Approximating the Partial Cover Problem, Journal of Algorithm, 39:137-144, 2001. PDF
  24. Bar-Noy A., R. Bar-Yehuda, A. Freund, S. Naor, and B. Schieber, A unified approach to approximating resource allocation and scheduling, Journal of the ACM 48(5):1069-1090, 2001. PDF
  25. Bar-Yehuda R., G. Even, J. Feldman, and S. Naor, Computing an optimal orientation of a balanced decomposition tree for linear arrangement problems, Journal of Graph Algorithms and Applications, 5:1-27, 2001.
  26. 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
  27. Bar-Yehuda, R. and D. Rawitz. Local ratio with negative weights, Operations Research Letters, 32(6):540-546, 2004. Link
  28. Bar-Yehuda, R. and Z. Kehat, Approximating the Dense Set-Cover Problem Journal of Computer and System Sciences 69(4):547-561, 2004. PS
  29. Bar-Yehuda, R., K. Bendel, A. Freund, and D. Rawitz, Local ratio: A unified framework for approximation algorithms in memoriam: Shimon Even 1935-2004, ACM Computing Surveys, 36, 4, 422-463, 2004. Pdf Journal link
  30. R. Bar-Yehuda, Even G., and S. Shahar, On approximating a geometric prize-collecting traveling salesman problem with time windows, Journal of Algorithms, 55(1):76-92 2005. Pdf
  31. Bar-Yehuda, R., D. Rawitz, On the Equivalence Between the Primal-Dual Schema and the Local-Ratio Technique, SIAM Journal on Discrete Mathematics 19(3):762-797, 2005.
  32. R. Bar-Yehuda and D. Rawitz, Using Fractional Primal-Dual to Schedule Split Intervals with Demands. Discrete Optimization 3(4): 275-287, 2006.
  33. Bar-Yehuda R., M. M. Halldorsson, J. Naor, H. Shachnai and I. Shapira, Scheduling Split Intervals, Siam Journal on Computing, Vol. 36, No. 1, 1-15, 2006.
  34. Bar-Yehuda R. and I. Yavneh, A Factor-Two Approximation Algorithm for Two-Dimensional Phase-Unwrapping, J. Graph Algorithms and Applications, 10, 2 123-139, 2006.
  35. R. Bar-Yehuda and J. Laserson, Exploiting Locality: Approximating Sorting Buffers, Journal of Discrete Algorithms, Vol. 5, Issue 4, 729-738, 2007.
  36. R. Bar-Yehuda I. Feldman and D. Rawitz, Improved Approximation Algorithm for Convex Recoloring of Trees. Theory of Computing Systems 43(1): 3-18, 2008.
  37. R. Zohar and R. Bar Yehuda The Maximum Weight Hierarchy Matching Problem, Information Fusion, 10, 2, 198-206, 2009.
  38. Bar-Yehuda R., M. Beder, Y. Cohen, and D. Rawitz. Resource allocation in bounded degree trees. Algorithmica, 54(1):89-106, 2009.
  39. Bar-Yehuda R, D. Hermelin and D. Rawitz, An Extension of the Nemhauser-Trotter Theorem to Generalized Vertex Cover with Applications. SIAM J. Discrete Math. 24(1):287-300, 2010.
  40. Bar-Yehuda R., G. Flysher, J. Mestre and D. Rawitz, Approximation of Partial Capacitated Vertex Cover, SIAM J. Discrete Math. Volume 24, Issue 4, pp. 1441-1469 (2010)
  41. Bar-Yehuda R., D. Hermelin and D. Rawitz. Minimum vertex cover in rectangle graphs. Computational Geometry: Theory and Applications, Vol. 44, Issue 1, 356-364, 2011
  42. Bar-Yehuda R. and D. Rawitz. A note on multicovering with disks. Computational Geometry: Theory and Applications 46(3):394-399, 2013.

  43. Amzallag D., R. Bar-Yehuda, D. Raz and G. Scalosub, Cell Selection in 4G Cellular Networks. Accepted to IEEE Transactions on Mobile Computing 2013.
  44. Bar-Yehuda R., G. Polevoy and D. Rawitz, Bandwidth allocation in cellular networks with multiple interferences. Discrete Applied Mathematics 194:23-26, 2015.

  45. Bar-Yehuda R., M. Beder, and D. Rawitz. A constant factor approximation algorithm for the storage allocation problem. Algorithmica 77(4):1105-1127, 2017.

  46. Bar-Yehuda R., G. Kutiel and D. Rawitz. 1.5-Approximation Algorithm for the 2-Convex Recoloring Problem Discrete Applied Mathematics, to appear 2017

  47. Reuven Bar-Yehuda, Keren Censor-Hillel, Gregory Schwartzmana, A Distributed (2+\(\epsilon\))-Approximation for Vertex Cover in O(\log\(\Delta\)/\(\epsilon\)\log\log\(\Delta\)) Rounds, Best Student Paper Award, PODC 2016 Invited to be submitted to the Special Issue of PODC 2016 in the Journal of the ACM (JACM). Journal of the ACM 64(3): 23:1-23:11 (2017). ACM 64(3): 23:1-23:11 (2017)

  48. Bar-Yehuda R., E. Kantor, S. Kutten, D. Rawitz, Growing Half-Balls: Minimizing Storage and Communication Costs in CDNs. SIAM Journal on Discrete Mathematics, 32(3):1903-1921, 2018.

next up previous
Next: Book Chapters Up: Refereed papers in professional Previous: Refereed papers in professional
& Bar-Yehuda 2020-09-27