Next: Book Chapters
Up: Refereed papers in professional
Previous: Refereed papers in professional
 BarYehuda, R. and S. Even.
A linear time approximation algorithm for the weighted vertex cover
problem.
Journal of Algorithms, 2:198203, 1981.
PDF
 BarYehuda, R. and U. Vishkin.
Complexity of finding kpathfree dominating sets in graphs.
Information Processing Letters, 14(5):228232, 1982.
 BarYehuda, R. and S. Moran.
On approximation problems related to the independent set and vertex cover problems.
Discrete Applied Mathematics, 9:110, 1984.
 BarYehuda, R. and S. Even.
A LocalRatio Theorem for Approximating the Weighted Vertex Cover
problem.
Annals of Discrete Mathematics, 25:2746, 1985.
PDF
 BarYehuda, R. and S. Kutten.
Fault tolerant distributed majority commitment.
Journal of Algorithms, 9(4):568582, December 1988.
 BarYehuda, 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 ComputerAided Design of Integrated
Circuits and Systems, 8(7), 1989.
Link
 BarYehuda, R., O. Goldreich, and A. Itai.
Efficient emulation of singlehop radio network with collision
detection on multihop radio network with no collision detection.
Distributed Computing, 5(2):6772, 1991.
PDF
 BarYehuda, R., O. Goldreich, and A. Itai.
On the timecomplexity of broadcast in multihop radio networks: An
exponential gap between determinism and randomization.
Journal of Computer and System Sciences, 45:104126, 1992.
PDF
 BarYehuda, R., T. Etzion, and S. Moran.
Rotatingtable games and derivatives of words.
Theoretical Computer Science, 108:311329, 1993.
Link
 BarYehuda, R. and S. Fogel.
Variations on ray shooting.
Algorithmica, 11:133145, 1994.
 BarYehuda, 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:2943, 1992.
 BarYehuda, R., B. Chor, E. Kushilevitz, and A. Orlitsky.
Privacy, additional information, and communication.
IEEE Transactions on Information Theory, 39(6):19301943,
1993.
 BarYehuda, R., A. Israeli, and A. Itai.
Multiple communication in multihop radio networks.
SIAM Journal on Computing, 22(4):875887, August 1993.
PDF
 BarYehuda, R. and B. Chazelle.
Triangulating disjoint Jordan chains.
Int. J. of Computational Geometry & Appl., 4(4):475481,
1994.
PDF
 BarYehuda, R. and E. BenHanoch.
A linear time algorithm for covering simple polygons with similar
rectangles.
Int. J. of Computational Geometry & Appl., 6(1):79102, 1996.
PDF
 BarYehuda, R. C. Gotsman.
Time/space tradeoffs for polygon mesh rendering.
ACM Trans. on Graphics, 15(2):141152, 1996.
PDF
 Cohen, S., G. Elber, and R. BarYehuda.
Matching of freeform curves.
Computer Aided Design, 29(5):369378, 1997.
PDF
 BarYehuda, 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):942959, 1998.
PDF
Download from SIAM electronic publication
 BarYehuda, R. and S. Fogel.
Partitioning a sequence into few monotone subsequences.
Acta Informatica, 35:421440, 1998.
Postscript
BibTeX+Abstract
 Becker, A., R. BarYehuda, and D. Geiger.
Randomized Algorithms for the Loop Cutset Problem,
Journal Artificial Intelligence Research 12:219234, 2000.
Download from JAIR electronic publication
 BarYehuda, R.,
One for the Price of Two: A Unified Approach
for Approximating Covering Problems,
Algorithmica 27(2), 2000:131144, 2000.
PDF
 BarYehuda, R. and D. Rawitz.
Efficient Algorithms for Integer Programs
with Two Variables per Constraint,
Algorithmica 29(4):595609, 2001.
PDF
 BarYehuda, R.,
Using Homogeneous Weights for Approximating
the Partial Cover Problem,
Journal of Algorithm, 39:137144, 2001.
PDF
 BarNoy A., R. BarYehuda, A. Freund, S. Naor, and B. Schieber,
A unified approach to approximating resource allocation and scheduling,
Journal of the ACM 48(5):10691090, 2001.
PDF
 BarYehuda 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:127, 2001.
 BarYehuda R. and D. Rawitz,
Approximating ElementWeighted Vertex Deletion Problems for the
Complete kpartite Property,
Journal of Algorithms, 42(1):2040, 2002
Link
 BarYehuda, R. and D. Rawitz.
Local ratio with negative weights,
Operations Research Letters,
32(6):540546, 2004.
Link
 BarYehuda, R. and Z. Kehat,
Approximating the Dense SetCover Problem
Journal of Computer and System Sciences
69(4):547561, 2004.
PS
 BarYehuda, R., K. Bendel, A. Freund, and D. Rawitz,
Local ratio: A unified framework for approximation algorithms in memoriam: Shimon Even 19352004,
ACM Computing Surveys, 36, 4, 422463, 2004.
Pdf
Journal link
 R. BarYehuda, Even G., and S. Shahar,
On approximating a geometric prizecollecting traveling salesman problem with time windows,
Journal of Algorithms, 55(1):7692 2005.
Pdf
 BarYehuda, R., D. Rawitz,
On the Equivalence Between the PrimalDual Schema and the LocalRatio Technique,
SIAM Journal on Discrete Mathematics 19(3):762797, 2005.
 R. BarYehuda and D. Rawitz,
Using Fractional PrimalDual to Schedule Split Intervals with Demands.
Discrete Optimization 3(4): 275287, 2006.
 BarYehuda R., M. M. Halldorsson, J. Naor, H. Shachnai and I. Shapira,
Scheduling Split Intervals,
Siam Journal on Computing, Vol. 36, No. 1, 115, 2006.
 BarYehuda R. and I. Yavneh,
A FactorTwo Approximation Algorithm for TwoDimensional PhaseUnwrapping,
J. Graph Algorithms and Applications, 10, 2 123139, 2006.
 R. BarYehuda and J. Laserson,
Exploiting Locality: Approximating Sorting Buffers,
Journal of Discrete Algorithms, Vol. 5, Issue 4, 729738, 2007.
 R. BarYehuda I. Feldman and D. Rawitz,
Improved Approximation Algorithm for Convex Recoloring of Trees.
Theory of Computing Systems 43(1): 318, 2008.
 R. Zohar and R. Bar Yehuda
The Maximum Weight Hierarchy Matching Problem,
Information Fusion, 10, 2, 198206, 2009.
 BarYehuda R., M. Beder, Y. Cohen, and D. Rawitz.
Resource allocation in bounded degree trees.
Algorithmica, 54(1):89106, 2009.
 BarYehuda R, D. Hermelin and D. Rawitz,
An Extension of the NemhauserTrotter Theorem to Generalized Vertex Cover with Applications.
SIAM J. Discrete Math. 24(1):287300, 2010.
 BarYehuda R., G. Flysher, J. Mestre and D. Rawitz,
Approximation of Partial Capacitated Vertex Cover,
SIAM J. Discrete Math. Volume 24, Issue 4, pp. 14411469 (2010)
 BarYehuda R., D. Hermelin and D. Rawitz.
Minimum vertex cover in rectangle graphs.
Computational Geometry: Theory and Applications,
Vol. 44, Issue 1, 356364, 2011
 BarYehuda R. and D. Rawitz.
A note on multicovering with disks.
Computational Geometry: Theory and Applications 46(3):394399, 2013.
 Amzallag D., R. BarYehuda, D. Raz and G. Scalosub,
Cell Selection in 4G Cellular Networks.
Accepted to IEEE Transactions on Mobile Computing 2013.
 BarYehuda R., G. Polevoy and D. Rawitz,
Bandwidth allocation in cellular networks with multiple interferences.
Discrete Applied Mathematics 194:2326, 2015.

BarYehuda R., M. Beder, and D. Rawitz.
A constant factor approximation algorithm for the storage allocation problem.
Algorithmica 77(4):11051127, 2017.

BarYehuda R., G. Kutiel and D. Rawitz.
1.5Approximation Algorithm for the 2Convex Recoloring Problem
Discrete Applied Mathematics, to appear 2017
 Reuven BarYehuda, Keren CensorHillel, Gregory Schwartzmana,
A Distributed (2+)Approximation
for Vertex Cover in O(\log/\log\log)
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:123:11 (2017). ACM 64(3): 23:123:11 (2017)
 BarYehuda R., E. Kantor, S. Kutten, D. Rawitz,
Growing HalfBalls: Minimizing Storage and Communication Costs in CDNs.
SIAM Journal on Discrete Mathematics, 32(3):19031921, 2018.
Next: Book Chapters
Up: Refereed papers in professional
Previous: Refereed papers in professional
& BarYehuda
20200927