{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:33:16Z","timestamp":1750221196645,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":27,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,7,11]],"date-time":"2018-07-11T00:00:00Z","timestamp":1531267200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001742","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1506\/16"],"award-info":[{"award-number":["1506\/16"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"publisher"}]},{"name":"ICRC Blavatnik Fund"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,7,11]]},"DOI":"10.1145\/3210377.3210407","type":"proceedings-article","created":{"date-parts":[[2018,7,12]],"date-time":"2018-07-12T17:46:44Z","timestamp":1531417604000},"page":"301-310","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["The Price of Bounded Preemption"],"prefix":"10.1145","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}]},{"given":"Yossi","family":"Azar","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}]},{"given":"Mark","family":"Berlin","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}]}],"member":"320","published-online":{"date-parts":[[2018,7,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974317.11"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0039-1"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0257-1"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-005-1172-z"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1099-1425(199911\/12)2:6<245::AID-JOS28>3.0.CO;2-5"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2003.09.004"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/502102.502107"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799354138"},{"key":"e_1_3_2_1_9_1","first-page":"27","article-title":"A local ratio theorem for approximating the weighted vertex cover problem","volume":"25","author":"Bar-Yehuda R.","year":"1985","unstructured":"R. Bar-Yehuda and S. Even . A local ratio theorem for approximating the weighted vertex cover problem . Ann. Discrete Math. , 25 : 27 -- 46 , 1985 . R. Bar-Yehuda and S. Even. A local ratio theorem for approximating the weighted vertex cover problem. Ann. Discrete Math., 25:27--46, 1985.","journal-title":"Ann. Discrete Math."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703437843"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2005.32"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2007.38"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TII.2012.2188805"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795283292"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(94)00116-T"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1066610"},{"key":"e_1_3_2_1_17_1","first-page":"75","article-title":"Optimization and approximation in deterministic sequencing and scheduling: A survey","volume":"5","author":"Graham R.","year":"1979","unstructured":"R. Graham , E. L. Lawler , J. Lenstra , and A. R. Kan . Optimization and approximation in deterministic sequencing and scheduling: A survey . Arm. Discr. Math. , 5 : 75 -- 90 , 1979 . R. Graham, E. L. Lawler, J. Lenstra, and A. R. Kan. Optimization and approximation in deterministic sequencing and scheduling: A survey. Arm. Discr. Math., 5:75--90, 1979.","journal-title":"Arm. Discr. Math."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1128"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_3_2_1_20_1","first-page":"27","article-title":"Sequencing to minimize the weighted number of tardy jobs. Rev. Franccaise d'Automatique, Informatique","volume":"10","author":"Lawler E. L.","year":"1976","unstructured":"E. L. Lawler . Sequencing to minimize the weighted number of tardy jobs. Rev. Franccaise d'Automatique, Informatique , Recherche Op\u00e9rationnel , 10 : 27 -- 33 , 05 1976 . E. L. Lawler. Sequencing to minimize the weighted number of tardy jobs. Rev. Franccaise d'Automatique, Informatique, Recherche Op\u00e9rationnel, 10:27--33, 05 1976.","journal-title":"Recherche Op\u00e9rationnel"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02248588"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0895-7177(94)90209-7"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.16.1.77"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.15.1.102"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.03.006"},{"key":"e_1_3_2_1_26_1","unstructured":"A. J.\n      Soper\n     and \n      V. A.\n      Strusevich\n  . \n  Power of Preemption on Uniform Parallel Machines\n  . In K. Jansen J. D. P. Rolim N. R. Devanur and C. Moore editors Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM \n  2014\n  ) volume \n  28\n   of \n  Leibniz International Proceedings in Informatics (LIPIcs) pages \n  392\n  --\n  402 Dagstuhl Germany 2014. Schloss Dagstuhl--Leibniz-Zentrum fuer \n  Informatik\n  .  A. J. Soper and V. A. Strusevich. Power of Preemption on Uniform Parallel Machines. In K. Jansen J. D. P. Rolim N. R. Devanur and C. Moore editors Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2014) volume 28 of Leibniz International Proceedings in Informatics (LIPIcs) pages 392--402 Dagstuhl Germany 2014. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_1_27_1","first-page":"328","volume-title":"Proc. 6th IEEE Int. Conf. Real-Time Comput. Syst. Appl. (RTCSA)","author":"Wang Y.","year":"1999","unstructured":"Y. Wang and M. Saksena . Scheduling fixed-priority tasks with preemption threshold . In Proc. 6th IEEE Int. Conf. Real-Time Comput. Syst. Appl. (RTCSA) , pages 328 -- 335 , 1999 . Y. Wang and M. Saksena. Scheduling fixed-priority tasks with preemption threshold. In Proc. 6th IEEE Int. Conf. Real-Time Comput. Syst. Appl. (RTCSA), pages 328--335, 1999."}],"event":{"name":"SPAA '18: 30th ACM Symposium on Parallelism in Algorithms and Architectures","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"],"location":"Vienna Austria","acronym":"SPAA '18"},"container-title":["Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3210377.3210407","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3210377.3210407","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:39:20Z","timestamp":1750210760000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3210377.3210407"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,11]]},"references-count":27,"alternative-id":["10.1145\/3210377.3210407","10.1145\/3210377"],"URL":"https:\/\/doi.org\/10.1145\/3210377.3210407","relation":{},"subject":[],"published":{"date-parts":[[2018,7,11]]},"assertion":[{"value":"2018-07-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}