{"id":22,"date":"2013-10-30T16:17:39","date_gmt":"2013-10-30T14:17:39","guid":{"rendered":"http:\/\/www.eng.biu.ac.il\/rawitzd\/?page_id=22"},"modified":"2022-10-14T13:49:55","modified_gmt":"2022-10-14T10:49:55","slug":"publications","status":"publish","type":"page","link":"https:\/\/www.eng.biu.ac.il\/rawitzd\/publications\/","title":{"rendered":"Publications"},"content":{"rendered":"<p><strong>Edited Books:<\/strong><\/p>\n<ul>\n<li>Guy Even and Dror Rawitz (Editors). Design and analysis of algorithms, <em>Mediterranean Conference on Algorithms<\/em> (MEDALG), LNCS 7659, Springer, 2012.<\/li>\n<\/ul>\n<hr \/>\n<p><strong>Book Chapters:<\/strong><\/p>\n<ol>\n<li>Reuven Bar-Yehuda, Keren Bendel, Ari Freund, and Dror Rawitz. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/LRscheduling.pdf\">The local ratio technique and its application to scheduling and resource allocation problems<\/a>. In\u00a0<i>Graph Theory, Combinatorics, and Algorithms: Interdisciplinary Applications<\/i>, Martin C. Golumbic, Irith Ben-Arroyo Hartman (Eds.), Operations Research &amp; Computer Science Series, Vol. 34:107-143, Springer-Verlag, 2005.<\/li>\n<li>Reuven Bar-Yehuda and Dror Rawitz. <a href=\"http:\/\/www.springerlink.com\/openurl.asp?genre=article&amp;issn=0302-9743&amp;volume=3895&amp;spage=196\">A tale of two methods<\/a>. In\u00a0<i><a href=\"http:\/\/www.springerlink.com\/openurl.asp?genre=issue&amp;issn=0302-9743&amp;volume=3895\">Theoretical Computer Science: Essays in Memory of Shimon Even<\/a><\/i>, Oded Goldreich, Arnold L. Rosenberg, and Alan L. Selman (Eds.), LNCS 3895:196-217, Springer-Verlag, 2006.<br \/>\nSee also\u00a0<a href=\"http:\/\/www.wisdom.weizmann.ac.il\/~oded\/even-book.html\">A book in memory of Shimon Even<\/a>.<\/li>\n<li>Dror Rawitz. Local Ratio. In <i>Handbook of Approximation Algorithms and Metaheuristics<\/i>, 2nd Edition: Methodologies and Traditional Applications, Volume 1, Chapter 6. Teoflio Gonzalez (Editor), Chapman &amp; Hall\/CRC, 2018.<\/li>\n<\/ol>\n<hr \/>\n<p><strong>Invited Papers:<\/strong><\/p>\n<ol>\n<li>Amotz Bar-Noy, Keerti Choudhary, David Peleg, and Dror Rawitz. Realizability of graph specifications: characterizations and algorithms. 25th SIROCCO, LNCS 11085:3-13, 2018.<\/li>\n<li>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.<\/li>\n<li>Amotz Bar-Noy, Toni B\u00f6hnlein, David Peleg, Mor Perry, and Dror Rawitz. Relaxed and approximate graph realizations. In 32nd IWOCA, LNCS 12757:3-19, 2021.<\/li>\n<li>Amotz Bar-Noy, Toni B\u00f6hnlein, David Peleg, and Dror Rawitz. On realizing a single degree sequence by a bipartite graph (SWAT), LIPIcs 227, 1:1-17, 2022.<\/li>\n<\/ol>\n<hr \/>\n<p><strong>Journal Papers:<\/strong><\/p>\n<ol>\n<li>Reuven Bar-Yehuda and Dror Rawitz. <a href=\"http:\/\/dx.doi.org\/10.1007\/s004530010075\">Efficient algorithms for integer programs with two variables per constraint<\/a>. <i>Algorithmica<\/i>\u00a029(4):595-609, 2001.<\/li>\n<li>Reuven Bar-Yehuda and Dror Rawitz. <a href=\"http:\/\/dx.doi.org\/10.1006\/jagm.2001.1196\">Approximating element-weighted vertex deletion problems for the complete k-partite property<\/a>. <i>Journal of Algorithms<\/i> 42(1):20-40, 2002.<\/li>\n<li>Reuven Bar-Yehuda and Dror Rawitz. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/neg.ps\">Local ratio with negative weights<\/a>. <i>Operations Research Letters<\/i>\u00a032(6):540-546, 2004.<\/li>\n<li>Reuven Bar-Yehuda, Keren Bendel, Ari Freund, and Dror Rawitz. <a href=\"http:\/\/doi.acm.org\/10.1145\/1041680.1041683\">Local Ratio: a unified framework for approximation algorithms<\/a>. <i>ACM Computing Surveys<\/i>\u00a036(4):422-463, 2004.<\/li>\n<li>Guy Even, Dror Rawitz, and Shimon (Moni) Shahar. <a href=\"http:\/\/authors.elsevier.com\/sd\/article\/S0020019005000906\">Hitting sets when the VC-dimension is small<\/a>. <i>Information Processing Letters<\/i>\u00a095(2): 358-362, 2005. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Talks\/VC-slides.pdf\">Slides<\/a><\/li>\n<li>Reuven Bar-Yehuda and Dror Rawitz. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/equiv.pdf\">On the equivalence between the primal-dual schema and the local ratio technique<\/a>. <i>SIAM Journal on Discrete Mathematics<\/i> 19(3):762-797, 2005.<\/li>\n<li>Erez Petrank and Dror Rawitz. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/cache.ps\">The hardness of cache conscious data placement<\/a>. <i>Nordic Journal of Computing<\/i>\u00a0 12(3):275-307, 2005.<\/li>\n<li>Reuven Bar-Yehuda and Dror Rawitz. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/frac.ps\">Using fractional primal-dual to schedule split intervals with demands<\/a>. <i>Discrete Optimization<\/i>\u00a03(4):275-287, 2006.<\/li>\n<li>Dror Rawitz. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/admission.pdf\">Admission control with advance reservations in simple networks<\/a>. <i>Journal of Discrete Algorithms<\/i>\u00a0 5(3):491-500, 2007.<\/li>\n<li>Reuven Bar-Yehuda, Ido Feldman, and Dror Rawitz. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/convex.ps\">Improved approximation algorithm for convex recoloring of trees<\/a>. <i>Theory of Computing Systems<\/i> 43(1):3-18, 2008 (special issue of WAOA'05).<\/li>\n<li>Maxime Crochemore, Danny Hermelin, Gad Landau, Dror Rawitz, and Stephane Vialette. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/2-intervals.ps\">Approximating the 2-interval pattern problem<\/a>. <i>Theoretical Computer Science<\/i> 395(2-3):283-297, 2008.<\/li>\n<li>Guy Even, Retsef Levi, Dror Rawitz, Baruch Schieber, Shimon (Moni) Shahar, and Maxim Sviridenko. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/stabbing.pdf\">Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs<\/a>. <i>ACM Transactions on Algorithms<\/i>\u00a0 4(3), 2008.<\/li>\n<li>Zvi Lotker, Boaz Patt-Shamir, and Dror Rawitz. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/2slopes.pdf\">Ski rental with two general options<\/a>. <i>Information Processing Letters<\/i>\u00a0108(6):339-422, 2008.<\/li>\n<li>Danny Hermelin, Dror Rawitz, Romeo Rizzi, and Stephane Vialette. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/substring.pdf\">The minimum substring cover problem<\/a>. <i>Information and Computation<\/i>\u00a0206(11):1303-1312, 2008.<\/li>\n<li>Amos Israeli, Dror Rawitz, and Oran Sharon. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/srp.pdf\">On the complexity of sequential rectangle placement in IEEE 802.16\/WiMAX systems<\/a>. <i>Information and Computation <\/i>206(11):1334-1345, 2008.<\/li>\n<li>Reuven Bar-Yehuda, Michael Beder, Yuval Cohen, and Dror Rawitz. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/alloc.pdf\">Resource allocation in bounded degree trees<\/a>. <i>Algorithmica\u00a0<\/i> 54(1):89-106, 2009.<\/li>\n<li>Rami Cohen, Dror Rawitz, and Danny Raz. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/multicast.pdf\">Time dependent multi scheduling of multicast<\/a>. <i>ACM Transactions on Algorithms\u00a0<\/i> 6(1), 2009.<\/li>\n<li>Ayelet Butman, Danny Hermelin, Moshe Lewenstein, and Dror Rawitz. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/multiple.pdf\">Optimization problems in multiple-interval graphs<\/a>. <i>ACM Transactions on Algorithms<\/i>\u00a06(2), 2010.<\/li>\n<li>Reuven Bar-Yehuda, Danny Hermelin, and Dror Rawitz. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/nt.pdf\">An extension of the Nemhauser&amp;Trotter Theorem to generalized vertex cover with applications<\/a>. <i>SIAM Journal on Discrete Mathematics<\/i>\u00a024(1):287-300, 2010.<\/li>\n<li>Reuven Bar-Yehuda, Guy Flysher, Julian Mestre, and Dror Rawitz. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/pcvc_demands.pdf\">Approximation of partial capacitated vertex cover<\/a>. <i>SIAM Journal on Discrete Mathematics <\/i>24(4):1441-1469, 2010.<\/li>\n<li>Danny Hermelin and Dror Rawitz. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/t-subtree.pdf\">Optimization problems in multiple subtree graphs<\/a>. <i>Discrete Applied Mathematics<\/i>\u00a0159(7):588-594, 2011.<\/li>\n<li>Reuven Bar-Yehuda, Danny Hermelin, and Dror Rawitz. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/rectangles.pdf\">Minimum vertex cover in rectangle graphs<\/a>. <i>Computational Geometry: Theory and Applications<\/i> 44(6-7):356-364, 2011.<\/li>\n<li>Boaz Patt-Shamir and Dror Rawitz. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/budget.pdf\">Video distribution under multiple constraints<\/a>. <i>Theoretical Computer Science\u00a0<\/i> 412(29):3717-3730, 2011.<\/li>\n<li>Dror Rawitz and Shimon (Moni) Shahar. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/d-interval.pdf\">Partial multicovering and the\u00a0<i>d<\/i>-consecutive ones property<\/a>. <i>Discrete Optimization<\/i>\u00a08(4):555-567, 2011.<\/li>\n<li>Boaz Patt-Shamir, Dror Rawitz, and Gabriel Scalosub. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/cell.pdf\">Distributed approximation of cellular coverage<\/a>. <i>Journal of Parallel and Distributed Computing<\/i>\u00a072:402-408, 2012.<\/li>\n<li>Boaz Patt-Shamir and Dror Rawitz. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/mvbp.pdf\">Vector bin packing with multiple-choice<\/a>. <i>Discrete Applied Mathematics<\/i>\u00a0 160(10-11):1591-1600, 2012.<\/li>\n<li>Bin Liu, Peter Terlecky, Amotz Bar-Noy, Ramesh Govindan, Micheal J. Neely, and Dror Rawitz. Optimizing information credibility in social swarming applications (<a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/credibility.pdf\">paper<\/a>\u00a0<a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/credibility-app.pdf\">appendix<\/a>). <i>IEEE Transactions on Parallel and Distributed Systems<\/i>\u00a023(6):1147-1158, 2012.<\/li>\n<li>Zvi Lotker, Boaz Patt-Shamir, and Dror Rawitz. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/ski.pdf\">Rent, lease or buy: randomized strategies for multislope ski rental<\/a>. <i>SIAM Journal on Discrete Mathematics<\/i>\u00a026(2):718-736, 2012.<\/li>\n<li>Yishay Mansour, Boaz Patt-Shamir, and Dror Rawitz. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/superpackets.pdf\">Overflow management with multipart packets<\/a>. <i>Computer Networks<\/i>\u00a056(15):3456-3467, 2012.<\/li>\n<li>Yuval Emek, Magn\u00fas M. Halld\u00f3rsson, Yishay Mansour, Boaz Patt-Shamir, Jaikumar Radhakrishnan, and Dror Rawitz. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/osp.pdf\">Online set packing<\/a>. <i>SIAM Journal on Computing<\/i>\u00a041(4):728-746, 2012.<\/li>\n<li>Dror Rawitz and Shimon Shahar. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/arc.pdf\">Capacitated arc stabbing<\/a>. <i>Journal of Discrete Algorithms<\/i>\u00a0 17:86-94, 2012.<\/li>\n<li>Reuven Bar-Yehuda and Dror Rawitz. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/disk.pdf\">A note on multicovering with disks<\/a>. <i>Computational Geometry: Theory and Applications<\/i>\u00a046(3):394-399, 2013.<\/li>\n<li>Magn\u00fas M. Halld\u00f3rsson, Boaz Patt-Shamir, and Dror Rawitz. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/conflicts.pdf\">Online scheduling with interval conflicts<\/a>. <i>Theory of Computing Systems<\/i>\u00a0 53(2):300-317, 2013 (special issue of STACS'11).<\/li>\n<li>Yishay Mansour, Boaz Patt-Shamir, and Dror Rawitz. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/links.pdf\">Competitive router scheduling with structured data<\/a>. <i>Theoretical Computer Science<\/i>\u00a0530:12-22, 2014.<\/li>\n<li>Danny Hermelin, Julian Mestre, and Dror Rawitz. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/dig.pdf\">Optimization problems in dotted interval graphs<\/a>. <i>Discrete Applied Mathematics<\/i>\u00a0174:66-72, 2014.<\/li>\n<li>Peter Terlecky, Brian Phelan, Amotz Bar-Noy, Theodore Brown, and Dror Rawitz. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/relays.pdf\">Should I stay or should I go? Maximizing lifetime with relays<\/a>. <i>Computer Networks<\/i>\u00a070:210-224, 2014.<\/li>\n<li>Bin Liu, Peter Terlecky, Xing Xu, Amotz Bar-Noy, Ramesh Govindan, and Dror Rawitz. Peer-assisted timely report delivery in social swarming applications. <i>IEEE Transactions on Wirelesss Communications<\/i> 13(10):5826-5838, 2014.<\/li>\n<li>Reuven Bar-Yehuda, Gleb Polevoy, and Dror Rawitz. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/interference.pdf\">Bandwidth allocation in cellular networks with multiple interferences<\/a>. <i>Discrete Applied Mathematics<\/i> 194:23-36, 2015.<\/li>\n<li>Amotz Bar-Noy, Ben Baumer, and Dror Rawitz. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/duty_cycle.pdf\">Changing of the guards: Strip cover with duty cycling<\/a>. <i>Theoretical Computer Science<\/i> 610:135-148, 2016 (special issue of SIROCCO'12).<\/li>\n<li>Pierre Fraigniaud, Magn\u00fas M. Halld\u00f3rsson, Boaz Patt-Shamir, Dror Rawitz, and Adi Rosen. Shrinking maxima, decreasing costs: New online packing and covering problems. <em>Algorithmica<\/em> 74(4): 1205-1223, 2016.<\/li>\n<li>Reuven Bar-Yehuda, Michael Beder and Dror Rawitz. A constant factor approximation algorithm for the storage allocation problem. <i>Algorithmica<\/i> 77(4):1105-1127, 2017.<\/li>\n<li>Amotz Bar-Noy, Dror Rawitz, and Peter Terlecky. Maximizing barrier coverage lifetime with mobile sensors. <i>SIAM Journal on Discrete Mathematics<\/i> 31(1):573-596, 2017.<\/li>\n<li>Amotz Bar-Noy, Ben Baumer and Dror Rawitz. <a href=\"http:\/\/arxiv.org\/abs\/1204.1082\">Set it and forget it: Approximating the set once strip cover problem<\/a>. <em>Algorithmica<\/em> 79(2):368-386, 2017.<\/li>\n<li>Magn\u00fas M. Halld\u00f3rsson, Sven K\u00f6hler, Boaz Patt-Shamir, and Dror Rawitz. Distributed backup placement in networks. <i>Distributed Computing<\/i> 31(2):83-98, 2018.<\/li>\n<li>Reuven Bar-Yehuda, Gilad Kutiel, and Dror Rawitz. 1.5-approximation algorithm for the 2-convex recoloring problem. <i>Discrete Applied Mathematics<\/i> 246:2-11 ,2018.<\/li>\n<li>Reuven Bar-Yehuda, Erez Kantor, Shay Kutten, and Dror Rawitz. Growing half-balls: Minimizing storage and communication costs in CDNs. <i>SIAM Journal on Discrete Mathematics<\/i> 32(3):1903-1921, 2018.<\/li>\n<li>Dror Rawitz and Ariella Voloshin. Flexible allocation on related machines with assignment restrictions. <i>Discrete Applied Mathematics<\/i> 250:309-321, 2018.<\/li>\n<li>Magn\u00fas M. Halld\u00f3rsson, Sven K\u00f6hler, and Dror Rawitz. Distributed approximation of <em>k<\/em>-service assignment. <i>Distributed Computing<\/i> 32(1):27-40, 2019.<\/li>\n<li>Gilad Kutiel and Dror Rawitz. Service chain placement in SDNs. <i>Discrete Applied Mathematics<\/i> 270:168-180, 2019.<\/li>\n<li>Amotz Bar-Noy, David Peleg, and Dror Rawitz. Vertex-weighted realizations of graphs. <i>Theoretical Computer Science<\/i> 807:56-72, 2020.<\/li>\n<li>Gilad Kutiel and Dror Rawitz. Local search algorithms for the maximum carpool matching problem. <em>Algorithmica<\/em> 82(11):3165-3182, 2020.<cite class=\"data\"><\/cite><\/li>\n<li>Amotz Bar-Noy, Keerti Choudhary, David Peleg, and Dror Rawitz. Efficiently Realizing Interval Sequences. <i>SIAM Journal on Discrete Mathematics<\/i> 34(4):2318-2337, 2020.<cite class=\"data\"><\/cite><\/li>\n<li>Ravi B. Boppana, Magn\u00fas M. Halld\u00f3rsson, and Dror Rawitz. Simple and local independent set approximation. Theoretical Computer Science 846:27-37, 2020 (special issue of SIROCCO'18).<cite class=\"data\"><\/cite><\/li>\n<li>Amotz Bar-Noy, Thomas Erlebach, Dror Rawitz, Peter Terlecky. \"Green\" barrier coverage with mobile sensors. <em>Theoretical Computer Science<\/em> 860:117-134, 2021.<\/li>\n<li>Dror Rawitz and Adi Ros\u00e9n. Online budgeted maximum coverage. Algorithmica 83(9):2989-3014, 2021.<\/li>\n<li>Amotz Bar-Noy, Toni B\u00f6hnlein, David Peleg, and Dror Rawitz. On Vertex-Weighted Realizations of Acyclic and General Graphs. <em>Theoretical Computer Science<\/em> 922:81-95, 2022.<\/li>\n<li>Menachem Poss and Dror Rawitz. Maximizing barrier coverage lifetime with static sensors. <em>Journal of Scheduling<\/em> 25(5):535-545, 2022.<\/li>\n<li><span title=\"Amotz Bar-Noy\">Amotz Bar-Noy<\/span>, <span title=\"Toni B\u00f6hnlein\">Toni B\u00f6hnlein<\/span>, <span title=\"Zvi Lotker\">Zvi Lotker<\/span>, <span title=\"David Peleg\">David Peleg<\/span>, Dror Rawitz. The generalized microscopic image reconstruction problem. Discrete Applied Mathematics 321:402-416, 2022.<\/li>\n<li>Amotz Bar-Noy, David Peleg, Mor Perry, and Dror Rawitz. Composed degree-distance realizations of graphs. <em>Algorithmica<\/em>, to appear (Special issue of IWOCA'21).<\/li>\n<\/ol>\n<hr \/>\n<p><strong>Refereed Conference Papers:<\/strong><\/p>\n<ol>\n<li>Reuven Bar-Yehuda and Dror Rawitz. Efficient algorithms for integer programs with two variables per constraint. 7th ESA, LNCS\u00a0 1643:116-126, 1999.<\/li>\n<li>Reuven Bar-Yehuda and Dror Rawitz. On the equivalence between the primal-dual schema and the local ratio technique. 4th APPROX, LNCS\u00a0 2129:24-35, 2001.\u00a0<a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Talks\/equiv.pdf\">Slides<\/a><\/li>\n<li>Erez Petrank and Dror Rawitz. The hardness of cache conscious data placement. 29th POPL, 101-112, 2002.\u00a0<a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Talks\/Cache.ppt\">Slides<\/a><\/li>\n<li>Ari Freund and Dror Rawitz. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/fitting.pdf\">Combinatorial interpretations of dual fitting and primal fitting<\/a>. 1st WAOA, LNCS\u00a0 2909:137-150, 2003.\u00a0<a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Talks\/fitting-talk.ppt\">Slides<\/a><\/li>\n<li>Rami Cohen, Dror Rawitz, and Danny Raz. Time dependent multi scheduling of multicast. 12th ESA, LNCS\u00a0 3221:216-227, 2004.<\/li>\n<li>Reuven Bar-Yehuda and Dror Rawitz. Using fractional primal-dual to schedule split intervals with demands. 13th ESA, LNCS\u00a0 3669:714-725, 2005.\u00a0<a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Talks\/frac-slides.pdf\">Slides<\/a><\/li>\n<li>Reuven Bar-Yehuda, Ido Feldman, and Dror Rawitz. Improved approximation algorithm for convex recoloring of trees. 3rd WAOA, LNCS\u00a0 3879:55-68, 2005.<\/li>\n<li>Guy Even, Dror Rawitz, and Shimon (Moni) Shahar. <a href=\"http:\/\/dx.doi.org\/10.1007\/11758471_5\">Approximation algorithms for capacitated rectangle stabbing<\/a>. 6th CIAC, LNCS\u00a0 3998:18-29, 2006.<\/li>\n<li>Reuven Bar-Yehuda, Michael Beder, Yuval Cohen, and Dror Rawitz. Resource allocation in bounded degree trees. 14th ESA, LNCS\u00a0 4168:64-75, 2006.\u00a0<a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Talks\/alloc-slides.pdf\">Slides<\/a><\/li>\n<li>Ayelet Butman, Danny Hermelin, Moshe Lewenstein, and Dror Rawitz. Optimization problems in multiple-interval graphs. 18th SODA, 268-277, 2007.\u00a0<a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Talks\/multiple-talk.pdf\">Slides<\/a><\/li>\n<li>Reuven Bar-Yehuda, Guy Flysher, Julian Mestre, and Dror Rawitz. Approximation of partial capacitated vertex cover. 15th ESA, LNCS\u00a0 4698:335-346, 2007.<\/li>\n<li>Amos Israeli, Dror Rawitz, and Oran Sharon. On the complexity of sequential rectangle placement in IEEE 802.16\/WiMAX systems. 15th ESA, LNCS\u00a0 4698:570-581, 2007.<\/li>\n<li>Danny Hermelin, Dror Rawitz, Romeo Rizzi, and Stephane Vialette. The minimum substring cover problem. 5th WAOA, LNCS\u00a0 4927:170-183, 2007.<\/li>\n<li>Zvi Lotker, Boaz Patt-Shamir, and Dror Rawitz. Rent, lease or buy: randomized strategies for multislope ski rental. 25th STACS, 503-514, 2008.\u00a0<a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Talks\/ski-talk.pdf\">Slides<\/a><\/li>\n<li>Boaz Patt-Shamir and Dror Rawitz. Video distribution under multiple constraints. 28th ICDCS, 841-848, 2008.\u00a0<a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Talks\/budget-talk.pdf\">Slides<\/a><\/li>\n<li>Boaz Patt-Shamir, Dror Rawitz, and Gabriel Scalosub. Distributed approximation of cellular coverage. 12th OPODIS, LNCS\u00a0 5401:331-345, 2008.<\/li>\n<li>Reuven Bar-Yehuda, Danny Hermelin, and Dror Rawitz. An extension of the Nemhauser&amp;Trotter Theorem to generalized vertex cover with applications. 7th WAOA, LNCS\u00a0 5893:13-24, 2009.\u00a0<a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Talks\/nt-talk.pdf\">Slides<\/a><\/li>\n<li>Danny Hermelin and Dror Rawitz. Optimization problems in multiple subtree graphs. 7th WAOA, LNCS\u00a0 5893:194-204, 2009.<\/li>\n<li>Boaz Patt-Shamir and Dror Rawitz. Vector bin packing with multiple-choice. 12th SWAT, LNCS\u00a0 6139:248-259, 2010.\u00a0<a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Talks\/mvbp-talk.pdf\">Slides<\/a><\/li>\n<li>Yuval Emek, Magn\u00fas M. Halld\u00f3rsson, Yishay Mansour, Boaz\u00a0 Patt-Shamir, Jaikumar Radhakrishnan, and Dror Rawitz. Online set packing and competitive scheduling of multipart tasks. 29th PODC, 440-449, 2010.\u00a0<a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Talks\/set_packing-talk.pdf\">Slides<\/a><\/li>\n<li>Reuven Bar-Yehuda, Danny Hermelin, and Dror Rawitz. Minimum vertex cover in rectangle graphs. 18th ESA, LNCS\u00a0 6346:255-266, 2010.<\/li>\n<li>Reuven Bar-Yehuda, Gleb Polevoy, and Dror Rawitz. Bandwidth allocation in cellular networks with multiple interferences. 6th DIALM-POMC, 33-42, 2010.<\/li>\n<li>Magn\u00fas M. Halld\u00f3rsson, Boaz Patt-Shamir, and Dror Rawitz. Online scheduling with interval conflicts. 28th STACS, 472-483, 2011.\u00a0<a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Talks\/conflicts-talk.pdf\">Slides<\/a><\/li>\n<li>Yishay Mansour, Boaz Patt-Shamir, and Dror Rawitz. Overflow management with multipart packets. 30th INFOCOM, 2606-2614, 2011.<\/li>\n<li>Yishay Mansour, Boaz Patt-Shamir, and Dror Rawitz. Competitive router scheduling with structured data. 9th WAOA, LNCS\u00a0 7164:219-232, 2011.\u00a0<a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Talks\/links-talk.pdf\">Slides<\/a><\/li>\n<li>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.\u00a0<b>Best paper<\/b>.<\/li>\n<li>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.<\/li>\n<li>Amotz Bar-Noy, Ben Baumer, and Dror Rawitz. Changing of the guards: Strip cover with duty cycling. 19th SIROCCO, LNCS\u00a0 7355:36-47, 2012.<\/li>\n<li>Reuven Bar-Yehuda, Erez Kantor, Shay Kutten, and Dror Rawitz. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/movie.pdf\">Growing half-balls: Minimizing storage and communication costs in CDNs<\/a>. 39th ICALP, LNCS 7392:416-427, 2012.<\/li>\n<li>Danny Hermelin, Julian Mestre, and Dror Rawitz. Optimization problems in dotted interval graphs. 38th WG, LNCS\u00a0 7551:46-56, 2012.<\/li>\n<li>Reuven Bar-Yehuda, Michael Beder, and Dror Rawitz. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Papers\/sap.pdf\">A constant factor approximation algorithm for the storage allocation problem<\/a>. 25th SPAA, 204-213, 2013.\u00a0<a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Talks\/sap-talk.pdf\">Slides<\/a><\/li>\n<li>Pierre Fraigniaud, Magn\u00fas M. Halld\u00f3rsson, Boaz Patt-Shamir, Dror Rawitz, and Adi Ros\u00e9n. Shrinking maxima, decreasing costs: New online packing and covering problems. 16th APPROX, LNCS\u00a0 8096:158-172, 2013.\u00a0<a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Talks\/opip-talk.pdf\">Slides<\/a><\/li>\n<li>Amotz Bar-Noy, Dror Rawitz, and Peter Terlecky. Maximizing barrier coverage lifetime with mobile sensors. 21st ESA, LNCS\u00a0 8125: 97-108, 2013.<\/li>\n<li>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\u2013991, 2014.<\/li>\n<li>Amotz Bar-Noy, Dror Rawitz, and Peter Terlecky. \"Green\" barrier coverage with mobile sensors. 9th CIAC, LNCS 9079:33-46, 2015.<\/li>\n<li>Magn\u00fas M. Halld\u00f3rsson, Sven K\u00f6hler, Boaz Patt-Shamir, and Dror Rawitz. Distributed backup placement in networks. 27th SPAA, 274-283, 2015.<\/li>\n<li>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.<\/li>\n<li>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.<\/li>\n<li>Magn\u00fas M. Halld\u00f3rsson, Sven K\u00f6hler, and Dror Rawitz. Distributed approximation of <em>k<\/em>-service assignment. 19th OPODIS, LIPIcs 46, 11:1-11:16, 2015.<\/li>\n<li>Dror Rawitz and Adi Ros\u00e9n. Online budgeted maximum coverage. 24th ESA, LIPIcs 57, 73:1-73:17, 2016.<\/li>\n<li>Dror Rawitz and Ariella Voloshin.\u00a0Flexible cell selection in cellular networks. 12th ALGOSENSORS, LNCS 10050:112-128, 2016.<\/li>\n<li>Gilad Kutiel and Dror Rawitz. Local search algorithms for the maximum carpool matching problem. 25th ESA, LIPIcs 87, 55:1-55:14, 2017.<\/li>\n<li>Menachem Poss and Dror Rawitz. Maximizing barrier coverage lifetime with static sensors. 13th ALGOSENSORS, LNCS 10718:198-210, 2017.<\/li>\n<li>Gilad Kutiel and Dror Rawitz. Service chain placement in SDNs. 3rd ALGOCLOUD, LNCS 10739:27-40, 2017.<\/li>\n<li>Guy Even, Moti Medina, and Dror Rawitz. Online Generalized Caching with Varying Weights and Costs. 30th SPAA, 205-212, 2018.<\/li>\n<li>Ravi B. Boppana, Magn\u00fas M. Halld\u00f3rsson, and Dror Rawitz. Simple and local independent set approximation. 25th SIROCCO, LNCS 11085:88-101, 2018.<\/li>\n<li>Amotz Bar-Noy, Keerti Choudhary, David Peleg, and Dror Rawitz. Efficiently Realizing Interval Sequences. 30th ISAAC, LIPIcs 149, 47:1-47:15, 2019.<\/li>\n<li>Amotz Bar-Noy, Toni B\u00f6hnlein, Zvi Lotker, David Peleg, and Dror Rawitz. The Generalized Microscopic Image Reconstruction Problem. 30th ISAAC, LIPIcs 149, 42:1-42:15,<cite class=\"data\"> <\/cite>2019<em>.<\/em><\/li>\n<li>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.<\/li>\n<li>Amotz Bar-Noy, Keerti Choudhary, Avi Cohen, David Peleg, and Dror Rawitz. Minimum Neighboring Degree Realization in Graphs and Trees. 28th ESA, 2020.<\/li>\n<li>Amotz Bar-Noy, Toni B\u00f6hnlein, Zvi Lotker, David Peleg, and Dror Rawitz. Weighted Microscopic Image Reconstruction. 47th SOFSEM, LNCS 12607:373-386, 2021.<\/li>\n<li>Amotz Bar-Noy, Toni B\u00f6hnlein, David Peleg, and Dror Rawitz. On vertex-weighted graph realizations. In 12th CIAC, LNCS 12701:90-102, 2021.<\/li>\n<li>Oren Katz, Dror Rawitz, Danny Raz. Containers Resource Allocation in Dynamic Cloud Environments. 20th IFIP Networking 1-9, 2021.<\/li>\n<li>Amotz Bar-Noy, David Peleg, Mor Perry, and Dror Rawitz. Composed degree-distance realizations of graphs. In 32nd IWOCA, LNCS 12757:63-77, 2021.<\/li>\n<li>Assaf Rabinowitz and Dror Rawitz. Overflow management with self-eliminations. In 17 ALGOSENSORS, LNCS 12961:124-139, 2021.<\/li>\n<li>Amotz Bar-Noy, David Peleg, Dror Rawitz, and Elad Yehezkel. Selected neighbor degree forest realization. In 32th ISAAC, LIPIcs 212, 27:1-15, 2021.<\/li>\n<li>Amotz Bar-Noy, Toni B\u00f6hnlein, David Peleg, and Dror Rawitz. Vertex-weighted graphs: realizable and unrealizable domains. In 16th WALCOM, LNCS 13174:315-327, 2022.<\/li>\n<li>Toni B\u00f6hnlein, Sapir Erlich, Zvi Lotker, and Dror Rawitz. Randomized strategies for non-additive 3-slope ski rental. In 29th SIROCCO, LNCS 13298:62-78, 2022.<\/li>\n<li>Amotz Bar-Noy, David Peleg, Mor Perry, and Dror Rawitz. Graph realization of distance sets. In 47th MFCS, 2022.<\/li>\n<li>Amotz Bar-Noy, Toni B\u00f6hnlein, David Peleg, and Dror Rawitz. On the role of the high-low partition in realizing a degree sequence by a bipartite graph. In 47th MFCS, 2022.<\/li>\n<\/ol>\n<hr \/>\n<p><strong>Brief Announcements:<\/strong><\/p>\n<ol>\n<li>Amotz Bar-Noy, Ben Baumer, and Dror Rawitz. <a href=\"http:\/\/arxiv.org\/abs\/1204.1082\">Set it and forget it: Approximating the set once strip cover problem<\/a>. 25th SPAA, 105-107, 2013. <a href=\"http:\/\/www.eng.biu.ac.il\/~rawitzd\/Talks\/set_once-talk.pdf\">Slides<\/a><\/li>\n<li>Ravi B. Boppana, Magn\u00fas M. Halld\u00f3rsson, and Dror Rawitz. Simple and Local Independent Set Approximation. 37th PODC 163-165, 2018.<\/li>\n<\/ol>\n<hr \/>\n<p><strong>Theses:<\/strong><\/p>\n<ul>\n<li>Efficient algorithms for integer programs with two variables per constraint.<br \/>\nM.Sc. Thesis, Department of Computer Science, Technion, Haifa, Israel, June, 1999.<\/li>\n<li>Combinatorial and LP-based methods for designing approximation algorithms.<br \/>\nPh.D. Thesis, Department of Computer Science, Technion, Haifa, Israel, November, 2003.<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Edited Books: Guy Even and Dror Rawitz (Editors). Design and analysis of algorithms, Mediterranean Conference on Algorithms (MEDALG), LNCS 7659, Springer, 2012. Book Chapters: Reuven Bar-Yehuda, Keren Bendel, Ari Freund, and Dror Rawitz. The local ratio technique and its application to scheduling and resource allocation problems. In\u00a0Graph Theory, Combinatorics, and Algorithms: Interdisciplinary Applications, Martin C. &hellip; <a href=\"https:\/\/www.eng.biu.ac.il\/rawitzd\/publications\/\" class=\"more-link\">Continue reading <span class=\"screen-reader-text\">Publications<\/span> <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"open","template":"","meta":{"footnotes":""},"class_list":["post-22","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/www.eng.biu.ac.il\/rawitzd\/wp-json\/wp\/v2\/pages\/22"}],"collection":[{"href":"https:\/\/www.eng.biu.ac.il\/rawitzd\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.eng.biu.ac.il\/rawitzd\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.eng.biu.ac.il\/rawitzd\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.eng.biu.ac.il\/rawitzd\/wp-json\/wp\/v2\/comments?post=22"}],"version-history":[{"count":173,"href":"https:\/\/www.eng.biu.ac.il\/rawitzd\/wp-json\/wp\/v2\/pages\/22\/revisions"}],"predecessor-version":[{"id":389,"href":"https:\/\/www.eng.biu.ac.il\/rawitzd\/wp-json\/wp\/v2\/pages\/22\/revisions\/389"}],"wp:attachment":[{"href":"https:\/\/www.eng.biu.ac.il\/rawitzd\/wp-json\/wp\/v2\/media?parent=22"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}