Approximation Algorithms Papers

Reuven Bar-Yehuda

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. BibTeX+Abstract

2.   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. BibTeX+Abstract

3.   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. BibTeX+Abstract

4.   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. (Also SODA94) BibTeX+Abstract Download from SIAM electronic publication

5.   Bar-Yehuda, R., One for the Price of Two: A Unified Approach for Approximating Covering Problems, APROX98 and to apear Algorithmica. PostScript BibTeX+Abstract

6.   Bar-Yehuda, R., Using Homogenous Weights for Approximating the Partial Cover Problem, SODA99. PostScript BibTeX+Abstract

7.   Bar-Yehuda, R. and D. Rawitz. Efficient Algorithms for Integer Programs with Two Variables per Constraint ESA99. PostScript BibTeX+Abstract

8.   Bar-Noy A., Bar-Yehuda, R., Freund A., Naor S., and B. Schieber, A Unified Approach to Approximating Resource Allocation and Scheduling to apear STOC00. PostScript BibTeX+Abstract

• About this document ...