Publications

Edited Books:

  • Guy Even and Dror Rawitz (Editors). Design and analysis of algorithms, Mediterranean Conference on Algorithms (MEDALG), LNCS 7659, Springer, 2012.

Book Chapters:

  1. Reuven Bar-Yehuda, Keren Bendel, Ari Freund, and Dror Rawitz. The local ratio technique and its application to scheduling and resource allocation problems. In Graph Theory, Combinatorics, and Algorithms: Interdisciplinary Applications, Martin C. Golumbic, Irith Ben-Arroyo Hartman (Eds.), Operations Research & Computer Science Series, Vol. 34:107-143, Springer-Verlag, 2005.
  2. Reuven Bar-Yehuda and Dror Rawitz. A tale of two methods. In Theoretical Computer Science: Essays in Memory of Shimon Even, Oded Goldreich, Arnold L. Rosenberg, and Alan L. Selman (Eds.), LNCS 3895:196-217, Springer-Verlag, 2006.
    See also A book in memory of Shimon Even.
  3. Dror Rawitz. Local Ratio. In Handbook of Approximation Algorithms and Metaheuristics, 2nd Edition: Methodologies and Traditional Applications, Volume 1, Chapter 6. Teoflio Gonzalez (Editor), Chapman & Hall/CRC, 2018.
  4. Amotz Bar-Noy, Keerti Choudhary, David Peleg, and Dror Rawitz. Realizability of graph specifications: characterizations and algorithms. 25th SIROCCO, LNCS 11085:3-13, 2018.
  5. Amotz Bar-Noy, Keerti Choudhary, David Peleg, and Dror Rawitz. Graph Profile Realizations and Applications to Social Networks. 13th WALCOM, LNCS 11355:3-14, 2019.

Journal Papers:

  1. Reuven Bar-Yehuda and Dror Rawitz. Efficient algorithms for integer programs with two variables per constraint. Algorithmica 29(4):595-609, 2001.
  2. Reuven Bar-Yehuda and Dror Rawitz. Approximating element-weighted vertex deletion problems for the complete k-partite property. Journal of Algorithms 42(1):20-40, 2002.
  3. Reuven Bar-Yehuda and Dror Rawitz. Local ratio with negative weights. Operations Research Letters 32(6):540-546, 2004.
  4. Reuven Bar-Yehuda, Keren Bendel, Ari Freund, and Dror Rawitz. Local Ratio: a unified framework for approximation algorithms. ACM Computing Surveys 36(4):422-463, 2004.
  5. Guy Even, Dror Rawitz, and Shimon (Moni) Shahar. Hitting sets when the VC-dimension is small. Information Processing Letters 95(2): 358-362, 2005. Slides
  6. Reuven Bar-Yehuda and Dror Rawitz. On the equivalence between the primal-dual schema and the local ratio technique. SIAM Journal on Discrete Mathematics 19(3):762-797, 2005.
  7. Erez Petrank and Dror Rawitz. The hardness of cache conscious data placement. Nordic Journal of Computing  12(3):275-307, 2005.
  8. Reuven Bar-Yehuda and Dror Rawitz. Using fractional primal-dual to schedule split intervals with demands. Discrete Optimization 3(4):275-287, 2006.
  9. Dror Rawitz. Admission control with advance reservations in simple networks. Journal of Discrete Algorithms  5(3):491-500, 2007.
  10. Reuven Bar-Yehuda, Ido Feldman, and Dror Rawitz. Improved approximation algorithm for convex recoloring of trees. Theory of Computing Systems 43(1):3-18, 2008 (special issue of WAOA'05).
  11. Maxime Crochemore, Danny Hermelin, Gad Landau, Dror Rawitz, and Stephane Vialette. Approximating the 2-interval pattern problem. Theoretical Computer Science 395(2-3):283-297, 2008.
  12. Guy Even, Retsef Levi, Dror Rawitz, Baruch Schieber, Shimon (Moni) Shahar, and Maxim Sviridenko. Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs. ACM Transactions on Algorithms  4(3), 2008.
  13. Zvi Lotker, Boaz Patt-Shamir, and Dror Rawitz. Ski rental with two general options. Information Processing Letters 108(6):339-422, 2008.
  14. Danny Hermelin, Dror Rawitz, Romeo Rizzi, and Stephane Vialette. The minimum substring cover problem. Information and Computation 206(11):1303-1312, 2008.
  15. Amos Israeli, Dror Rawitz, and Oran Sharon. On the complexity of sequential rectangle placement in IEEE 802.16/WiMAX systems. Information and Computation 206(11):1334-1345, 2008.
  16. Reuven Bar-Yehuda, Michael Beder, Yuval Cohen, and Dror Rawitz. Resource allocation in bounded degree trees. Algorithmica  54(1):89-106, 2009.
  17. Rami Cohen, Dror Rawitz, and Danny Raz. Time dependent multi scheduling of multicast. ACM Transactions on Algorithms  6(1), 2009.
  18. Ayelet Butman, Danny Hermelin, Moshe Lewenstein, and Dror Rawitz. Optimization problems in multiple-interval graphs. ACM Transactions on Algorithms 6(2), 2010.
  19. Reuven Bar-Yehuda, Danny Hermelin, and Dror Rawitz. An extension of the Nemhauser&Trotter Theorem to generalized vertex cover with applications. SIAM Journal on Discrete Mathematics 24(1):287-300, 2010.
  20. Reuven Bar-Yehuda, Guy Flysher, Julian Mestre, and Dror Rawitz. Approximation of partial capacitated vertex cover. SIAM Journal on Discrete Mathematics 24(4):1441-1469, 2010.
  21. Danny Hermelin and Dror Rawitz. Optimization problems in multiple subtree graphs. Discrete Applied Mathematics 159(7):588-594, 2011.
  22. Reuven Bar-Yehuda, Danny Hermelin, and Dror Rawitz. Minimum vertex cover in rectangle graphs. Computational Geometry: Theory and Applications 44(6-7):356-364, 2011.
  23. Boaz Patt-Shamir and Dror Rawitz. Video distribution under multiple constraints. Theoretical Computer Science  412(29):3717-3730, 2011.
  24. Dror Rawitz and Shimon (Moni) Shahar. Partial multicovering and the d-consecutive ones property. Discrete Optimization 8(4):555-567, 2011.
  25. Boaz Patt-Shamir, Dror Rawitz, and Gabriel Scalosub. Distributed approximation of cellular coverage. Journal of Parallel and Distributed Computing 72:402-408, 2012.
  26. Boaz Patt-Shamir and Dror Rawitz. Vector bin packing with multiple-choice. Discrete Applied Mathematics  160(10-11):1591-1600, 2012.
  27. Bin Liu, Peter Terlecky, Amotz Bar-Noy, Ramesh Govindan, Micheal J. Neely, and Dror Rawitz. Optimizing information credibility in social swarming applications (paper appendix). IEEE Transactions on Parallel and Distributed Systems 23(6):1147-1158, 2012.
  28. Zvi Lotker, Boaz Patt-Shamir, and Dror Rawitz. Rent, lease or buy: randomized strategies for multislope ski rental. SIAM Journal on Discrete Mathematics 26(2):718-736, 2012.
  29. Yishay Mansour, Boaz Patt-Shamir, and Dror Rawitz. Overflow management with multipart packets. Computer Networks 56(15):3456-3467, 2012.
  30. Yuval Emek, Magnús M. Halldórsson, Yishay Mansour, Boaz Patt-Shamir, Jaikumar Radhakrishnan, and Dror Rawitz. Online set packing. SIAM Journal on Computing 41(4):728-746, 2012.
  31. Dror Rawitz and Shimon Shahar. Capacitated arc stabbing. Journal of Discrete Algorithms  17:86-94, 2012.
  32. Reuven Bar-Yehuda and Dror Rawitz. A note on multicovering with disks. Computational Geometry: Theory and Applications 46(3):394-399, 2013.
  33. Magnús M. Halldórsson, Boaz Patt-Shamir, and Dror Rawitz. Online scheduling with interval conflicts. Theory of Computing Systems  53(2):300-317, 2013 (special issue of STACS'11).
  34. Yishay Mansour, Boaz Patt-Shamir, and Dror Rawitz. Competitive router scheduling with structured data. Theoretical Computer Science 530:12-22, 2014.
  35. Danny Hermelin, Julian Mestre, and Dror Rawitz. Optimization problems in dotted interval graphs. Discrete Applied Mathematics 174:66-72, 2014.
  36. Peter Terlecky, Brian Phelan, Amotz Bar-Noy, Theodore Brown, and Dror Rawitz. Should I stay or should I go? Maximizing lifetime with relays. Computer Networks 70:210-224, 2014.
  37. Bin Liu, Peter Terlecky, Xing Xu, Amotz Bar-Noy, Ramesh Govindan, and Dror Rawitz. Peer-assisted timely report delivery in social swarming applications. IEEE Transactions on Wirelesss Communications 13(10):5826-5838, 2014.
  38. Reuven Bar-Yehuda, Gleb Polevoy, and Dror Rawitz. Bandwidth allocation in cellular networks with multiple interferences. Discrete Applied Mathematics 194:23-36, 2015.
  39. Amotz Bar-Noy, Ben Baumer, and Dror Rawitz. Changing of the guards: Strip cover with duty cycling. Theoretical Computer Science 610:135-148, 2016 (special issue of SIROCCO'12).
  40. Pierre Fraigniaud, Magnús M. Halldórsson, Boaz Patt-Shamir, Dror Rawitz, and Adi Rosen. Shrinking maxima, decreasing costs: New online packing and covering problems. Algorithmica 74(4): 1205-1223, 2016.
  41. Reuven Bar-Yehuda, Michael Beder and Dror Rawitz. A constant factor approximation algorithm for the storage allocation problem. Algorithmica 77(4):1105-1127, 2017.
  42. Amotz Bar-Noy, Dror Rawitz, and Peter Terlecky. Maximizing barrier coverage lifetime with mobile sensors. SIAM Journal on Discrete Mathematics 31(1):573-596, 2017.
  43. Amotz Bar-Noy, Ben Baumer and Dror Rawitz. Set it and forget it: Approximating the set once strip cover problem. Algorithmica 79(2):368-386, 2017.
  44. Magnús M. Halldórsson, Sven Köhler, Boaz Patt-Shamir, and Dror Rawitz. Distributed backup placement in networks. Distributed Computing 31(2):83-98, 2018.
  45. Reuven Bar-Yehuda, Gilad Kutiel, and Dror Rawitz. 1.5-approximation algorithm for the 2-convex recoloring problem. Discrete Applied Mathematics 246:2-11 ,2018.
  46. Reuven Bar-Yehuda, Erez Kantor, Shay Kutten, and Dror Rawitz. Growing half-balls: Minimizing storage and communication costs in CDNs. SIAM journal on Discrete Mathematics 32(3):1903-1921, 2018.
  47. Dror Rawitz and Ariella Voloshin. Flexible allocation on related machines with assignment restrictions. Discrete Applied Mathematics 250:309-321, 2018.
  48. Magnús M. Halldórsson, Sven Köhler, and Dror Rawitz. Distributed approximation of k-service assignment. Distributed Computing 32(1):27-40, 2019.
  49. Gilad Kutiel and Dror Rawitz. Service chain placement in SDNs. Discrete Applied Mathematics 270:168-180, 2019.
  50. Amotz Bar-Noy, David Peleg, and Dror Rawitz. Vertex-weighted realizations of graphs. Theoretical Computer Science 807:56-72, 2020.
  51. Gilad Kutiel and Dror Rawitz. Local search algorithms for the maximum carpool matching problem. Algorithmica 82(11):3165-3182, 2020.
  52. Amotz Bar-Noy, Keerti Choudhary, David Peleg, and Dror Rawitz. Efficiently Realizing Interval Sequences. SIAM journal on Discrete Mathematics 34(4):2318-2337, 2020.
  53. Ravi B. Boppana, Magnús M. Halldórsson, and Dror Rawitz. Simple and local independent set approximation. Theoretical Computer Science 846:27-37, 2020 (special issue of SIROCCO'18).
  54. Amotz Bar-Noy, Thomas Erlebach, Dror Rawitz, Peter Terlecky. "Green" barrier coverage with mobile sensors. Theoretical Computer Science 860:117-134, 2021.


Refereed Conference Papers:

  1. Reuven Bar-Yehuda and Dror Rawitz. Efficient algorithms for integer programs with two variables per constraint. 7th ESA, LNCS  1643:116-126, 1999.
  2. Reuven Bar-Yehuda and Dror Rawitz. On the equivalence between the primal-dual schema and the local ratio technique. 4th APPROX, LNCS  2129:24-35, 2001. Slides
  3. Erez Petrank and Dror Rawitz. The hardness of cache conscious data placement. 29th POPL, 101-112, 2002. Slides
  4. Ari Freund and Dror Rawitz. Combinatorial interpretations of dual fitting and primal fitting. 1st WAOA, LNCS  2909:137-150, 2003. Slides
  5. Rami Cohen, Dror Rawitz, and Danny Raz. Time dependent multi scheduling of multicast. 12th ESA, LNCS  3221:216-227, 2004.
  6. Reuven Bar-Yehuda and Dror Rawitz. Using fractional primal-dual to schedule split intervals with demands. 13th ESA, LNCS  3669:714-725, 2005. Slides
  7. Reuven Bar-Yehuda, Ido Feldman, and Dror Rawitz. Improved approximation algorithm for convex recoloring of trees. 3rd WAOA, LNCS  3879:55-68, 2005.
  8. Guy Even, Dror Rawitz, and Shimon (Moni) Shahar. Approximation algorithms for capacitated rectangle stabbing. 6th CIAC, LNCS  3998:18-29, 2006.
  9. Reuven Bar-Yehuda, Michael Beder, Yuval Cohen, and Dror Rawitz. Resource allocation in bounded degree trees. 14th ESA, LNCS  4168:64-75, 2006. Slides
  10. Ayelet Butman, Danny Hermelin, Moshe Lewenstein, and Dror Rawitz. Optimization problems in multiple-interval graphs. 18th SODA, 268-277, 2007. Slides
  11. Reuven Bar-Yehuda, Guy Flysher, Julian Mestre, and Dror Rawitz. Approximation of partial capacitated vertex cover. 15th ESA, LNCS  4698:335-346, 2007.
  12. Amos Israeli, Dror Rawitz, and Oran Sharon. On the complexity of sequential rectangle placement in IEEE 802.16/WiMAX systems. 15th ESA, LNCS  4698:570-581, 2007.
  13. Danny Hermelin, Dror Rawitz, Romeo Rizzi, and Stephane Vialette. The minimum substring cover problem. 5th WAOA, LNCS  4927:170-183, 2007.
  14. Zvi Lotker, Boaz Patt-Shamir, and Dror Rawitz. Rent, lease or buy: randomized strategies for multislope ski rental. 25th STACS, 503-514, 2008. Slides
  15. Boaz Patt-Shamir and Dror Rawitz. Video distribution under multiple constraints. 28th ICDCS, 841-848, 2008. Slides
  16. Boaz Patt-Shamir, Dror Rawitz, and Gabriel Scalosub. Distributed approximation of cellular coverage. 12th OPODIS, LNCS  5401:331-345, 2008.
  17. Reuven Bar-Yehuda, Danny Hermelin, and Dror Rawitz. An extension of the Nemhauser&Trotter Theorem to generalized vertex cover with applications. 7th WAOA, LNCS  5893:13-24, 2009. Slides
  18. Danny Hermelin and Dror Rawitz. Optimization problems in multiple subtree graphs. 7th WAOA, LNCS  5893:194-204, 2009.
  19. Boaz Patt-Shamir and Dror Rawitz. Vector bin packing with multiple-choice. 12th SWAT, LNCS  6139:248-259, 2010. Slides
  20. Yuval Emek, Magnús M. Halldórsson, Yishay Mansour, Boaz  Patt-Shamir, Jaikumar Radhakrishnan, and Dror Rawitz. Online set packing and competitive scheduling of multipart tasks. 29th PODC, 440-449, 2010. Slides
  21. Reuven Bar-Yehuda, Danny Hermelin, and Dror Rawitz. Minimum vertex cover in rectangle graphs. 18th ESA, LNCS  6346:255-266, 2010.
  22. Reuven Bar-Yehuda, Gleb Polevoy, and Dror Rawitz. Bandwidth allocation in cellular networks with multiple interferences. 6th DIALM-POMC, 33-42, 2010.
  23. Magnús M. Halldórsson, Boaz Patt-Shamir, and Dror Rawitz. Online scheduling with interval conflicts. 28th STACS, 472-483, 2011. Slides
  24. Yishay Mansour, Boaz Patt-Shamir, and Dror Rawitz. Overflow management with multipart packets. 30th INFOCOM, 2606-2614, 2011.
  25. Yishay Mansour, Boaz Patt-Shamir, and Dror Rawitz. Competitive router scheduling with structured data. 9th WAOA, LNCS  7164:219-232, 2011. Slides
  26. Peter Terlecky, Brian Phelan, Amotz Bar-Noy, Theodore Brown, and Dror Rawitz. Should I stay or should I go? Maximizing lifetime with relays. 8th DCOSS, 1-8, 2012. Best paper.
  27. Bin Liu, Peter Terlecky, Xing Xu, Amotz Bar-Noy, Ramesh Govindan, and Dror Rawitz. Peer-assisted timely report delivery in social swarming applications. 8th DCOSS, 75-82, 2012.
  28. Amotz Bar-Noy, Ben Baumer, and Dror Rawitz. Changing of the guards: Strip cover with duty cycling. 19th SIROCCO, LNCS  7355:36-47, 2012.
  29. Reuven Bar-Yehuda, Erez Kantor, Shay Kutten, and Dror Rawitz. Growing half-balls: Minimizing storage and communication costs in CDNs. 39th ICALP, LNCS 7392:416-427, 2012.
  30. Danny Hermelin, Julian Mestre, and Dror Rawitz. Optimization problems in dotted interval graphs. 38th WG, LNCS  7551:46-56, 2012.
  31. Reuven Bar-Yehuda, Michael Beder, and Dror Rawitz. A constant factor approximation algorithm for the storage allocation problem. 25th SPAA, 204-213, 2013. Slides
  32. Pierre Fraigniaud, Magnús M. Halldórsson, Boaz Patt-Shamir, Dror Rawitz, and Adi Rosén. Shrinking maxima, decreasing costs: New online packing and covering problems. 16th APPROX, LNCS  8096:158-172, 2013. Slides
  33. Amotz Bar-Noy, Dror Rawitz, and Peter Terlecky. Maximizing barrier coverage lifetime with mobile sensors. 21st ESA, LNCS  8125: 97-108, 2013.
  34. Prithwish Basu, Feng Yu, Amotz Bar-Noy, and Dror Rawitz. To sample or to smash? Estimating reachability in large time-varying graphs. Poster, 14th SDM, 983–991, 2014.
  35. Amotz Bar-Noy, Dror Rawitz, and Peter Terlecky. "Green" barrier coverage with mobile sensors. 9th CIAC, LNCS 9079:33-46, 2015.
  36. Magnús M. Halldórsson, Sven Köhler, Boaz Patt-Shamir, and Dror Rawitz. Distributed backup placement in networks. 27th SPAA, 274-283, 2015.
  37. Amotz Bar-Noy, Matthew P. Johnson, Nooreddin Naghibolhosseini, Dror Rawitz, and Simon Shamoun. The price of incorrectly aggregating coverage values in sensor selection. 11th DCOSS, 98-107, 2015.
  38. Reuven Bar-Yehuda, Gilad Kutiel, and Dror Rawitz. 1.5-approximation algorithm for the 2-convex recoloring problem. 26th IWOCA, LNCS 9538:299-311, 2015.
  39. Magnús M. Halldórsson, Sven Köhler, and Dror Rawitz. Distributed approximation of k-service assignment. 19th OPODIS, LIPIcs 46, 11:1-11:16, 2015.
  40. Dror Rawitz and Adi Rosén. Online budgeted maximum coverage. 24th ESA, LIPIcs 57, 73:1-73:17, 2016.
  41. Dror Rawitz and Ariella Voloshin. Flexible cell selection in cellular networks. 12th ALGOSENSORS, LNCS 10050:112-128, 2016.
  42. Gilad Kutiel and Dror Rawitz. Local search algorithms for the maximum carpool matching problem. 25th ESA, LIPIcs 87, 55:1-55:14, 2017.
  43. Menachem Poss and Dror Rawitz. Maximizing barrier coverage lifetime with static sensors. 13th ALGOSENSORS, LNCS 10718:198-210, 2017.
  44. Gilad Kutiel and Dror Rawitz. Service chain placement in SDNs. 3rd ALGOCLOUD, LNCS 10739:27-40, 2017.
  45. Guy Even, Moti Medina, and Dror Rawitz. Online Generalized Caching with Varying Weights and Costs. 30th SPAA, 205-212, 2018.
  46. Ravi B. Boppana, Magnús M. Halldórsson, and Dror Rawitz. Simple and local independent set approximation. 25th SIROCCO, LNCS 11085:88-101, 2018.
  47. Amotz Bar-Noy, Keerti Choudhary, David Peleg, and Dror Rawitz. Efficiently Realizing Interval Sequences. 30th ISAAC, LIPIcs 149, 47:1-47:15, 2019.
  48. Amotz Bar-Noy, Toni Böhnlein, Zvi Lotker, David Peleg, and Dror Rawitz. The Generalized Microscopic Image Reconstruction Problem. 30th ISAAC, LIPIcs 149, 42:1-42:15, 2019.
  49. Amotz Bar-Noy, Keerti Choudhary, David Peleg, and Dror Rawitz. Graph Realizations: Maximum Degree in Vertex Neighborhoods. 17th SWAT LIPIcs 162, 10:1-10:17, 2020.
  50. Amotz Bar-Noy, Keerti Choudhary, Avi Cohen, David Peleg, and Dror Rawitz. Minimum Neighboring Degree Realization in Graphs and Trees. 28th ESA, 2020.
  51. Amotz Bar-Noy, Toni Böhnlein, Zvi Lotker, David Peleg, and Dror Rawitz. Weighted Microscopic Image Reconstruction. 47th SOFSEM, 2021.
  52. Oren Katz, Dror Rawitz, Danny Raz. Containers Resource Allocation in Dynamic Cloud Environments. IFIP Networking 2021.

Brief Announcements:

  1. Amotz Bar-Noy, Ben Baumer, and Dror Rawitz. Set it and forget it: Approximating the set once strip cover problem. 25th SPAA, 105-107, 2013. Slides
  2. Ravi B. Boppana, Magnús M. Halldórsson, and Dror Rawitz. Simple and Local Independent Set Approximation. 37th PODC 163-165, 2018.

Theses:

  • Efficient algorithms for integer programs with two variables per constraint.
    M.Sc. Thesis, Department of Computer Science, Technion, Haifa, Israel, June, 1999.
  • Combinatorial and LP-based methods for designing approximation algorithms.
    Ph.D. Thesis, Department of Computer Science, Technion, Haifa, Israel, November, 2003.