-
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 )
-
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)
-
The Primal Dual Method for Approximation Algorithms, Set cover, see:
Vazirani's notes: Chapter 13 pages 69-72
(PDF)
-
Bar-Yehuda, R., Using Homogeneous Weights for Approximating the Partial Cover
Problem, Journal of Algorithm, 39, 137-144, 2001.
( PDF )
-
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 )
-
Reuven Bar-Yehuda, Danny Hermelin and Dror Rawitz.
Minimum vertex cover in rectangle graphs.
Computational Geometry: Theory and Applications.
( PDF )
-
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 )
-
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
-
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 )
-
Bar-Yehuda R. and D. Rawitz.
A note on multicovering with disks. Computational Geometry,
Theory and Applications 46(3):394-399, 2013
( PDF )
-
Julian Mestre,
Adaptive Local Ratio. SODA 2008 (received the Best Student Paper Award)
(PDF)
( PDF2 )
-
M. X. Goemans and D. P. Williamson.
A General Approximation Technique for Constrained Forest Problems
(PDF)
-
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
-
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
-
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)
-
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 )
-
Reuven Cohen Liran Katzir Danny Raz
An Efficient Approximation for the Generalized assignment Problem, IPL 2006
( PDF )
-
Daniel Lokshtanov, Pranabendu Misra, Joydeep Mukherjee, Fahad Panolan, Geevarghese Philip, Saket Saurabh,
2-Approximating Feedback Vertex Set in Tournaments
( PDF )
-
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 )
-
Reuven Bar-Yehuda and Jonathan Laserson
Exploiting Locality: Approximating Sorting Buffers,
WAOA 2005,
( PDF )
-
Reuven Bar-Yehuda, Michael Beder, Yuval Cohen, and Dror Rawitz.
Resource allocation in bounded degree trees.
Algorithmica, 54(1):89-106, 2009.
( PDF )
-
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 )
-
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 )
-
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 )
-
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.
-
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 )
-
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 )
-
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
-
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:167188
( PDF )
-
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
-
Shai Gutner,
Elementary approximation algorithms for prize collecting Steiner tree problems,
IPL, 107, 1, 30 , 39-44 , 2008
( PDF )
-
Zhenbo Wang., Zhenhua Cui
Combination of parallel machine scheduling and vertex cover
Theoretical Computer Science 460 (2012) 10-15
( PDF2 )
-
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 )
-
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 )
-
Julia'n Mestre, Jose' Verschae,
A 4-approximation for scheduling on a single machine with general cost function
( PDF )
-
Yaping Zhang, Yishuo Shi, Zhao Zhang
Approximation algorithm for the minimum weight connected k-subgraph cover problem
Theoretical Computer Science 05/2014
( PDF )
-
Samuel Fiorini, Gwenaël Joret, Oliver Schaudt,
Improved approximation algorithms for hitting 3-vertex paths,
( LINK )
( PDF )
-
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)