{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:09Z","timestamp":1740109329220,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2024,7,18]],"date-time":"2024-07-18T00:00:00Z","timestamp":1721260800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,7,18]],"date-time":"2024-07-18T00:00:00Z","timestamp":1721260800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100014037","name":"National Defense Science and Engineering Graduate","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100014037","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1733808","CCF-2006664"],"award-info":[{"award-number":["CCF-1733808","CCF-2006664"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"FinTech@CSAIL"},{"name":"National Science Foundation TRIPODS","award":["CCF-1740751"],"award-info":[{"award-number":["CCF-1740751"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,9]]},"DOI":"10.1007\/s00453-024-01252-1","type":"journal-article","created":{"date-parts":[[2024,7,18]],"date-time":"2024-07-18T11:01:37Z","timestamp":1721300497000},"page":"2997-3026","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["New Partitioning Techniques and Faster Algorithms for Approximate Interval Scheduling"],"prefix":"10.1007","volume":"86","author":[{"given":"Spencer","family":"Compton","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Slobodan","family":"Mitrovi\u0107","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ronitt","family":"Rubinfeld","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,7,18]]},"reference":[{"issue":"2","key":"1252_CR1","doi-asserted-by":"publisher","first-page":"131","DOI":"10.15623\/ijret.2013.0202008","volume":"2","author":"P Salot","year":"2013","unstructured":"Salot, P.: A survey of various scheduling algorithm in cloud computing environment. Int. J. Res. Eng. Technol. 2(2), 131\u2013135 (2013)","journal-title":"Int. J. Res. Eng. Technol."},{"key":"1252_CR2","first-page":"461","volume":"64","author":"R Sharma","year":"2010","unstructured":"Sharma, R., Soni, V.K., Mishra, M.K., Bhuyan, P.: A survey of job scheduling and resource management in grid computing. World Acad. Sci Eng. Technol. 64, 461\u2013466 (2010)","journal-title":"World Acad. Sci Eng. Technol."},{"issue":"5","key":"1252_CR3","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1002\/nav.20231","volume":"54","author":"AW Kolen","year":"2007","unstructured":"Kolen, A.W., Lenstra, J.K., Papadimitriou, C.H., Spieksma, F.C.: Interval scheduling: a survey. Naval Res. Logist. 54(5), 530\u2013543 (2007)","journal-title":"Naval Res. Logist."},{"issue":"6","key":"1252_CR4","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1287\/opre.47.6.873","volume":"47","author":"A Mingozzi","year":"1999","unstructured":"Mingozzi, A., Boschetti, M.A., Ricciardelli, S., Bianco, L.: A set partitioning approach to the crew scheduling problem. Oper. Res. 47(6), 873\u2013888 (1999)","journal-title":"Oper. Res."},{"issue":"1","key":"1252_CR5","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1145\/2455.214106","volume":"32","author":"DS Hochbaum","year":"1985","unstructured":"Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM 32(1), 130\u2013136 (1985)","journal-title":"J. ACM"},{"issue":"3\u20134","key":"1252_CR6","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/S0925-7721(98)00028-5","volume":"11","author":"PK Agarwal","year":"1998","unstructured":"Agarwal, P.K., Van Kreveld, M., Suri, S.: Label placement by maximum independent set in rectangles. Comput. Geom. 11(3\u20134), 209\u2013218 (1998)","journal-title":"Comput. Geom."},{"doi-asserted-by":"crossref","unstructured":"Verweij, B., Aardal, K.: An optimisation algorithm for maximum independent set with applications in map labelling. In: European Symposium on Algorithms, pp. 426\u2013437. Springer (1999)","key":"1252_CR7","DOI":"10.1007\/3-540-48481-7_37"},{"unstructured":"Bhore, S., Cardinal, J., Iacono, J., Koumoutsos, G.: Dynamic geometric independent set (2020). arXiv preprint arXiv:2007.08643","key":"1252_CR8"},{"unstructured":"Henzinger, M., Neumann, S., Wiese, A.: Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles. In: 36th International Symposium on Computational Geometry (SoCG 2020). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2020)","key":"1252_CR9"},{"unstructured":"Gawrychowski, P., Pokorski, K.: Sublinear dynamic interval scheduling (on one or multiple machines) (2022). arXiv preprint arXiv:2203.14310","key":"1252_CR10"},{"doi-asserted-by":"crossref","unstructured":"Gavruskin, A., Khoussainov, B., Kokho, M., Liu, J.: Dynamic interval scheduling for multiple machines. In: International Symposium on Algorithms and Computation, pp. 235\u2013246. Springer (2014)","key":"1252_CR11","DOI":"10.1007\/978-3-319-13075-0_19"},{"key":"1252_CR12","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/j.tcs.2014.09.046","volume":"562","author":"A Gavruskin","year":"2015","unstructured":"Gavruskin, A., Khoussainov, B., Kokho, M., Liu, J.: Dynamic algorithms for monotonic interval scheduling problem. Theoret. Comput. Sci. 562, 227\u2013242 (2015)","journal-title":"Theoret. Comput. Sci."},{"unstructured":"Frank, A.: Some polynomial algorithms for certain graphs and hypergraphs. In: Proceedings of the 5th British Combinatorial Conference. Utilitas Mathematica (1975)","key":"1252_CR13"},{"key":"1252_CR14","volume-title":"Algorithm Design","author":"E Tardos","year":"2005","unstructured":"Tardos, E., Kleinberg, J.: Algorithm Design. Pearson (2005)"},{"issue":"1","key":"1252_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0166-218X(87)90037-0","volume":"18","author":"EM Arkin","year":"1987","unstructured":"Arkin, E.M., Silverberg, E.B.: Scheduling jobs with fixed start and end times. Discrete Appl. Math. 18(1), 1\u20138 (1987)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"1252_CR16","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1287\/opre.26.1.22","volume":"26","author":"JK Lenstra","year":"1978","unstructured":"Lenstra, J.K., Rinnooy Kan, A.: Complexity of scheduling under precedence constraints. Oper. Res. 26(1), 22\u201335 (1978)","journal-title":"Oper. Res."},{"issue":"4","key":"1252_CR17","doi-asserted-by":"publisher","first-page":"1005","DOI":"10.1287\/moor.1050.0158","volume":"30","author":"JR Correa","year":"2005","unstructured":"Correa, J.R., Schulz, A.S.: Single-machine scheduling with precedence constraints. Math. Oper. Res. 30(4), 1005\u20131021 (2005)","journal-title":"Math. Oper. Res."},{"unstructured":"Robert, J., Schabanel, N.: Non-clairvoyant scheduling with precedence constraints. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 491\u2013500 (2008)","key":"1252_CR18"},{"issue":"4","key":"1252_CR19","doi-asserted-by":"publisher","first-page":"788","DOI":"10.1137\/S0097539702415007","volume":"34","author":"M Skutella","year":"2005","unstructured":"Skutella, M., Uetz, M.: Stochastic machine scheduling with precedence constraints. SIAM J. Comput. 34(4), 788\u2013802 (2005)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"1252_CR20","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1109\/TII.2012.2188805","volume":"9","author":"GC Buttazzo","year":"2012","unstructured":"Buttazzo, G.C., Bertogna, M., Yao, G.: Limited preemptive scheduling for real-time systems: a survey. IEEE Trans. Ind. Inf. 9(1), 3\u201315 (2012)","journal-title":"IEEE Trans. Ind. Inf."},{"key":"1252_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-2361-4","volume-title":"Scheduling","author":"M Pinedo","year":"2012","unstructured":"Pinedo, M.: Scheduling, vol. 29. Springer, Berlin (2012)"},{"key":"1252_CR22","first-page":"16","volume":"8","author":"E Levey","year":"2019","unstructured":"Levey, E., Rothvoss, T.: A (1+ epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies. SIAM J. Comput. 8, 16\u2013201 (2019)","journal-title":"SIAM J. Comput."},{"unstructured":"Cardinal, J., Iacono, J., Koumoutsos, G.: Worst-case efficient dynamic geometric independent set. In: 29th Annual European Symposium on Algorithms (ESA 2021), vol. 204, p. 25. Schloss Dagstuhl-Leibniz-Zentrum fur Informatik (2021)","key":"1252_CR23"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01252-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01252-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01252-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T07:06:39Z","timestamp":1725433599000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01252-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,18]]},"references-count":23,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["1252"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01252-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2024,7,18]]},"assertion":[{"value":"18 August 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 July 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 July 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"We have no conflict of interest to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}