Reuven Bar-Yehuda

According to our database1, Reuven Bar-Yehuda
  • authored at least 82 papers between 1981 and 2017.
  • has a "Dijkstra number"2 of four.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2017
A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) Rounds.
J. ACM, 2017

Distributed Approximation of Maximum Independent Set and Maximum Matching.
CoRR, 2017

A Constant Factor Approximation Algorithm for the Storage Allocation Problem.
Algorithmica, 2017

Distributed Approximation of Maximum Independent Set and Maximum Matching.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2017

2016
A Distributed $(2+ε)$-Approximation for Vertex Cover in $O(\logΔ/ε\log\logΔ)$ Rounds.
CoRR, 2016

A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) Rounds.
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

2015
Bandwidth allocation in cellular networks with multiple interferences.
Discrete Applied Mathematics, 2015

1.5-Approximation Algorithm for the 2-Convex Recoloring Problem.
Proceedings of the Combinatorial Algorithms - 26th International Workshop, 2015

2014
Random Algorithms for the Loop Cutset Problem.
CoRR, 2014

2013
Cell Selection in 4G Cellular Networks.
IEEE Trans. Mob. Comput., 2013

A note on multicovering with disks.
Comput. Geom., 2013

A constant factor approximation algorithm for the storage allocation problem: extended abstract.
Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures, 2013

2012
Growing Half-Balls: Minimizing Storage and Communication Costs in CDNs.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011
Randomized Algorithms for the Loop Cutset Problem
CoRR, 2011

Minimum vertex cover in rectangle graphs.
Comput. Geom., 2011

2010
An Extension of the Nemhauser--Trotter Theorem to Generalized Vertex Cover with Applications.
SIAM J. Discrete Math., 2010

Approximation of Partial Capacitated Vertex Cover.
SIAM J. Discrete Math., 2010

Minimum Vertex Cover in Rectangle Graphs
CoRR, 2010

Minimum Vertex Cover in Rectangle Graphs.
Proceedings of the Algorithms, 2010

Bandwidth allocation in cellular networks with multiple interferences.
Proceedings of the DIALM-POMC Joint Workshop on Foundations of Mobile Computing, 2010

2009
The maximum weight hierarchy matching problem.
Information Fusion, 2009

Resource Allocation in Bounded Degree Trees.
Algorithmica, 2009

Extension of the Nemhauser and Trotter Theorem to Generalized Vertex Cover with Applications.
Proceedings of the Approximation and Online Algorithms, 7th International Workshop, 2009

2008
Improved Approximation Algorithm for Convex Recoloring of Trees.
Theory Comput. Syst., 2008

Cell Selection in 4G Cellular Networks.
Proceedings of the INFOCOM 2008. 27th IEEE International Conference on Computer Communications, 2008

2007
Exploiting locality: approximating sorting buffers.
J. Discrete Algorithms, 2007

Approximation of Partial Capacitated Vertex Cover.
Proceedings of the Algorithms, 2007

2006
Scheduling Split Intervals.
SIAM J. Comput., 2006

A Factor-Two Approximation Algorithm for Two-Dimensional Phase Unwrapping.
J. Graph Algorithms Appl., 2006

Using fractional primal-dual to schedule split intervals with demands.
Discrete Optimization, 2006

Resource Allocation in Bounded Degree Trees.
Proceedings of the Algorithms, 2006

A Tale of Two Methods.
Proceedings of the Theoretical Computer Science, 2006

2005
On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique.
SIAM J. Discrete Math., 2005

On approximating a geometric prize-collecting traveling salesman problem with time windows.
J. Algorithms, 2005

Exploiting Locality: Approximating Sorting Buffers.
Proceedings of the Approximation and Online Algorithms, Third International Workshop, 2005

Improved Approximation Algorithm for Convex Recoloring of Trees.
Proceedings of the Approximation and Online Algorithms, Third International Workshop, 2005

Using Fractional Primal-Dual to Schedule Split Intervals with Demands.
Proceedings of the Algorithms, 2005

2004
Local ratio with negative weights.
Oper. Res. Lett., 2004

Approximating the dense set-cover problem.
J. Comput. Syst. Sci., 2004

Local ratio: A unified framework for approxmation algrithms in memoriam: Shimon Even 1935-2004.
ACM Comput. Surv., 2004

2003
On Approximating a Geometric Prize-Collecting Traveling Salesman Problem with Time Windows: Extended Abstract.
Proceedings of the Algorithms, 2003

2002
Approximating Element-Weighted Vertex Deletion Problems for the Complete k-Partite Property.
J. Algorithms, 2002

Scheduling split intervals.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

2001
Computing an Optimal Orientation of a Balanced Decomposition Tree for Linear Arrangement Problems.
J. Graph Algorithms Appl., 2001

Using Homogeneous Weights for Approximating the Partial Cover Problem.
J. Algorithms, 2001

A unified approach to approximating resource allocation and scheduling.
J. ACM, 2001

Efficient Algorithms for Integer Programs with Two Variables per Constraint.
Algorithmica, 2001

On the Equivalence between the Primal-Dual Schema and the Local-Ratio Technique.
Proceedings of the Approximation, 2001

2000
Randomized Algorithms for the Loop Cutset Problem.
J. Artif. Intell. Res., 2000

One for the Price of Two: a Unified Approach for Approximating Covering Problems.
Algorithmica, 2000

A unified approach to approximating resource allocation and scheduling.
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

1999
Random Algorithms for the Loop Cutset Problem.
Proceedings of the UAI '99: Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence, Stockholm, Sweden, July 30, 1999

Using Homogenous Weights for Approximating the Partial Cover Problem.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Geometric algorithms for message filtering in decentralized virtual environments.
Proceedings of the 1999 Symposium on Interactive 3D Graphics, 1999

Efficient Algorithms for Integer Programs with Two Variables per Constraint.
Proceedings of the Algorithms, 1999

1998
Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference.
SIAM J. Comput., 1998

Partitioning a Sequence into Few Monotone Subsequences.
Acta Inf., 1998

One for the Price of Two: A Unified Approach for Approximating Covering Problems.
Proceedings of the Approximation Algorithms for Combinatorial Optimization, 1998

1997
Matching of freeform curves.
Computer-Aided Design, 1997

1996
Time/Space Tradeoffs for Polygon Mesh Rendering.
ACM Trans. Graph., 1996

A linear time algorithm for covering simple polygons with similar rectangles.
Int. J. Comput. Geometry Appl., 1996

1994
Triangulating disjoint Jordan chains.
Int. J. Comput. Geometry Appl., 1994

Variations on Ray Shooting.
Algorithmica, 1994

Approximation Algorithms for the Vertex Feedback Set Problem with Applications to Constraint Satisfaction and Bayesian Inference.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

1993
Privacy, additional information and communication.
IEEE Trans. Information Theory, 1993

Rotating-Table Games and Derivatives of Words.
Theor. Comput. Sci., 1993

Multiple Communication in Multihop Radio Networks.
SIAM J. Comput., 1993

A Simple Algorithm for Maintaining the Center of a Planar Point-set.
Proceedings of the 5th Canadian Conference on Computational Geometry, 1993

1992
On the Time-Complexity of Broadcast in Multi-hop Radio Networks: An Exponential Gap Between Determinism and Randomization.
J. Comput. Syst. Sci., 1992

Connections Between two Cycles - a New Design of Dense Processor Interconnection Networks.
Discrete Applied Mathematics, 1992

1991
Efficient Emulation of Single-Hop Radio Network with Collision Detection on Multi-Hop Radio Network with no Collision Detection.
Distributed Computing, 1991

1990
Privacy, Additional Information, and Communication.
Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

1989
Depth-first-search and dynamic programming algorithms for efficient CMOS cell generation.
IEEE Trans. on CAD of Integrated Circuits and Systems, 1989

Efficient Emulation of Single-Hop Radio Network with Collision Detection on Multi-Hop Radio Network with no Collision Detection.
Proceedings of the Distributed Algorithms, 1989

Multiple Communication in Multi-Hop Radio Networks.
Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing, 1989

1988
Fault Tolerant Distributed Majority Commitment.
J. Algorithms, 1988

1987
Making Distributed Spanning Tree Algorithms Fault-Resilient.
Proceedings of the STACS 87, 1987

On the Time-Complexity of Broadcast in Radio Networks: An Exponential Gap Between Determinism and Randomization.
Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, 1987

1984
On approximation problems related to the independent set and vertex cover problems.
Discrete Applied Mathematics, 1984

1982
Complexity of Finding k-Path-Free Dominating Sets in Graphs.
Inf. Process. Lett., 1982

On Approximating a Vertex Cover for Planar Graphs
Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982

1981
A Linear-Time Approximation Algorithm for the Weighted Vertex Cover Problem.
J. Algorithms, 1981


  Loading...