{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T04:15:33Z","timestamp":1785557733472,"version":"3.56.0"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031929311","type":"print"},{"value":"9783031929328","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-92932-8_1","type":"book-chapter","created":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T07:47:14Z","timestamp":1747468034000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Exact and\u00a0Approximate High-Multiplicity Scheduling on\u00a0Identical Machines"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8358-6796","authenticated-orcid":false,"given":"Klaus","family":"Jansen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8066-4004","authenticated-orcid":false,"given":"Kai","family":"Kahler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Esther","family":"Zwanger","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,5,18]]},"reference":[{"issue":"3","key":"1_CR1","doi-asserted-by":"publisher","first-page":"2152","DOI":"10.1137\/17M1162792","volume":"28","author":"I Aliev","year":"2018","unstructured":"Aliev, I., De Loera, J.A., Eisenbrand, F., Oertel, T., Weismantel, R.: The support of integer optimal solutions. SIAM J. Optim. 28(3), 2152\u20132157 (2018). https:\/\/doi.org\/10.1137\/17M1162792","journal-title":"SIAM J. Optim."},{"key":"1_CR2","doi-asserted-by":"publisher","unstructured":"Berndt, S., Jansen, K., Klein, K.: New bounds for the vertices of the integer hull. In: SOSA, pp. 25\u201336. SIAM (2021). https:\/\/doi.org\/10.1137\/1.9781611976496.3","DOI":"10.1137\/1.9781611976496.3"},{"key":"1_CR3","doi-asserted-by":"publisher","unstructured":"Buchem, M., Rohwedder, L., Vredeveld, T., Wiese, A.: Additive approximation schemes for load balancing problems. In: ICALP. LIPIcs, vol.\u00a0198, pp. 42:1\u201342:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2021.42","DOI":"10.4230\/LIPIcs.ICALP.2021.42"},{"issue":"1","key":"1_CR4","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/BF01191202","volume":"12","author":"W Cook","year":"1992","unstructured":"Cook, W., Hartmann, M., Kannan, R., McDiarmid, C.: On integer points in polyhedra. Comb. 12(1), 27\u201337 (1992). https:\/\/doi.org\/10.1007\/BF01191202","journal-title":"Comb."},{"key":"1_CR5","doi-asserted-by":"publisher","unstructured":"Cslovjecsek, J., Eisenbrand, F., Hunkenschr\u00f6der, C., Rohwedder, L., Weismantel, R.: Block-structured integer and linear programming in strongly polynomial and near linear time. In: SODA, pp. 1666\u20131681. SIAM (2021). https:\/\/doi.org\/10.1137\/1.9781611976465.101","DOI":"10.1137\/1.9781611976465.101"},{"key":"1_CR6","doi-asserted-by":"publisher","unstructured":"Cslovjecsek, J., Eisenbrand, F., Weismantel, R.: N-fold integer programming via LP rounding. CoRR abs\/2002.07745 (2020). https:\/\/doi.org\/10.48550\/arXiv.2002.07745","DOI":"10.48550\/arXiv.2002.07745"},{"key":"1_CR7","doi-asserted-by":"publisher","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3","DOI":"10.1007\/978-3-319-21275-3"},{"key":"1_CR8","doi-asserted-by":"publisher","unstructured":"Eisenbrand, F., Hunkenschr\u00f6der, C., Klein, K.: Faster algorithms for integer programs with block structure. In: ICALP. LIPIcs, vol.\u00a0107, pp. 49:1\u201349:13. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.49","DOI":"10.4230\/LIPIcs.ICALP.2018.49"},{"key":"1_CR9","doi-asserted-by":"publisher","unstructured":"Eisenbrand, F., Weismantel, R.: Proximity results and faster algorithms for integer programming using the Steinitz lemma. ACM Trans. Algorithms 16(1) (2019). https:\/\/doi.org\/10.1145\/3340322","DOI":"10.1145\/3340322"},{"key":"1_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/J.JCSS.2016.06.004","volume":"84","author":"M Etscheid","year":"2017","unstructured":"Etscheid, M., Kratsch, S., Mnich, M., R\u00f6glin, H.: Polynomial kernels for weighted problems. J. Comput. Syst. Sci. 84, 1\u201310 (2017). https:\/\/doi.org\/10.1016\/J.JCSS.2016.06.004","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"1_CR11","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF02579200","volume":"7","author":"A Frank","year":"1987","unstructured":"Frank, A., Tardos, E.: An application of simultaneous Diophantine approximation in combinatorial optimization. Comb. 7(1), 49\u201365 (1987). https:\/\/doi.org\/10.1007\/BF02579200","journal-title":"Comb."},{"key":"1_CR12","doi-asserted-by":"publisher","unstructured":"Goemans, M.X., Rothvoss, T.: Polynomiality for bin packing with a constant number of item types. J. ACM 67(6) (2020). https:\/\/doi.org\/10.1145\/3421750","DOI":"10.1145\/3421750"},{"key":"1_CR13","unstructured":"Govzmann, A., Mnich, M., Omlor, S.: Faster algorithms for parallel and related machine scheduling (2023, manuscript)"},{"key":"1_CR14","doi-asserted-by":"publisher","unstructured":"Graham, R., Lawler, E., Lenstra, J., Kan, A.: Optimization and approximation in deterministic sequencing and scheduling: a survey. In: Hammer, P., Johnson, E., Korte, B. (eds.) Discrete Optimization II, Annals of Discrete Mathematics, vol.\u00a05, pp. 287\u2013326. Elsevier (1979). https:\/\/doi.org\/10.1016\/S0167-5060(08)70356-X","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"1_CR15","unstructured":"Hartmann, M.E.: Cutting planes and the complexity of the integer hull. Ph.D. thesis, Cornell University (1989)"},{"key":"1_CR16","unstructured":"Jansen, K., Kahler, K.: Faster algorithms for multitype cone and polytope intersection. Manuscript (Personal Communication)"},{"key":"1_CR17","doi-asserted-by":"publisher","unstructured":"Jansen, K., Kahler, K., Zwanger, E.: Exact and approximate high-multiplicity scheduling on identical machines. CoRR abs\/2404.17274 (2024). https:\/\/doi.org\/10.48550\/arXiv.2404.17274","DOI":"10.48550\/arXiv.2404.17274"},{"issue":"4","key":"1_CR18","doi-asserted-by":"publisher","first-page":"1498","DOI":"10.1287\/moor.2019.1040","volume":"45","author":"K Jansen","year":"2020","unstructured":"Jansen, K., Klein, K.M.: About the structure of the integer cone and its application to bin packing. Math. Oper. Res. 45(4), 1498\u20131511 (2020). https:\/\/doi.org\/10.1287\/moor.2019.1040","journal-title":"Math. Oper. Res."},{"issue":"3","key":"1_CR19","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1287\/MOOR.12.3.415","volume":"12","author":"R Kannan","year":"1987","unstructured":"Kannan, R.: Minkowski\u2019s convex body theorem and integer programming. Math. Oper. Res. 12(3), 415\u2013440 (1987). https:\/\/doi.org\/10.1287\/MOOR.12.3.415","journal-title":"Math. Oper. Res."},{"issue":"1","key":"1_CR20","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s10107-022-01882-9","volume":"200","author":"D Knop","year":"2023","unstructured":"Knop, D., Kouteck\u00fd, M., Levin, A., Mnich, M., Onn, S.: High-multiplicity N-fold IP via configuration LP. Math. Program. 200(1), 199\u2013227 (2023). https:\/\/doi.org\/10.1007\/s10107-022-01882-9","journal-title":"Math. Program."},{"issue":"5","key":"1_CR21","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/s10951-017-0550-0","volume":"21","author":"D Knop","year":"2018","unstructured":"Knop, D., Kouteck\u00fd, M.: Scheduling meets N-fold integer programming. J. Sched. 21(5), 493\u2013503 (2018). https:\/\/doi.org\/10.1007\/s10951-017-0550-0","journal-title":"J. Sched."},{"issue":"6","key":"1_CR22","doi-asserted-by":"publisher","first-page":"908","DOI":"10.1016\/j.orl.2021.11.005","volume":"49","author":"D Knop","year":"2021","unstructured":"Knop, D., Kouteck\u00fd, M., Levin, A., Mnich, M., Onn, S.: Parameterized complexity of configuration integer programs. Oper. Res. Lett. 49(6), 908\u2013913 (2021). https:\/\/doi.org\/10.1016\/j.orl.2021.11.005","journal-title":"Oper. Res. Lett."},{"key":"1_CR23","doi-asserted-by":"publisher","unstructured":"Kouteck\u00fd, M., Zink, J.: Complexity of scheduling few types of jobs on related and unrelated machines. In: ISAAC. LIPIcs, vol.\u00a0181, pp. 18:1\u201318:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2020.18","DOI":"10.4230\/LIPIcs.ISAAC.2020.18"},{"key":"1_CR24","doi-asserted-by":"publisher","unstructured":"Kowalik, L., Lassota, A., Majewski, K., Pilipczuk, M., Sokolowski, M.: Detecting points in integer cones of polytopes is double-exponentially hard. In: SOSA, pp. 279\u2013285. SIAM (2024). https:\/\/doi.org\/10.1137\/1.9781611977936.25","DOI":"10.1137\/1.9781611977936.25"},{"key":"1_CR25","doi-asserted-by":"publisher","unstructured":"Lenstra, J.K., Shmoys, D.B.: Elements of scheduling. CoRR abs\/2001.06005 (2020). https:\/\/doi.org\/10.48550\/arXiv.2001.06005","DOI":"10.48550\/arXiv.2001.06005"},{"issue":"1","key":"1_CR26","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/2422.322418","volume":"31","author":"N Megiddo","year":"1984","unstructured":"Megiddo, N.: Linear programming in linear time when the dimension is fixed. J. ACM 31(1), 114\u2013127 (1984). https:\/\/doi.org\/10.1145\/2422.322418","journal-title":"J. ACM"},{"key":"1_CR27","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1016\/j.cor.2018.07.020","volume":"100","author":"M Mnich","year":"2018","unstructured":"Mnich, M., van Bevern, R.: Parameterized complexity of machine scheduling: 15 open problems. Comput. Oper. Res. 100, 254\u2013261 (2018). https:\/\/doi.org\/10.1016\/j.cor.2018.07.020","journal-title":"Comput. Oper. Res."},{"issue":"1\u20132","key":"1_CR28","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/s10107-014-0830-9","volume":"154","author":"M Mnich","year":"2015","unstructured":"Mnich, M., Wiese, A.: Scheduling and fixed-parameter tractability. Math. Program. 154(1\u20132), 533\u2013562 (2015). https:\/\/doi.org\/10.1007\/s10107-014-0830-9","journal-title":"Math. Program."},{"key":"1_CR29","doi-asserted-by":"publisher","unstructured":"Zolotykh, N.Y.: On the number of vertices in integer linear programming problems. CoRR math\/0611356 (2006). https:\/\/doi.org\/10.48550\/arXiv.math\/0611356","DOI":"10.48550\/arXiv.math\/0611356"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-92932-8_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T07:47:17Z","timestamp":1747468037000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-92932-8_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031929311","9783031929328"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-92932-8_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"18 May 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Rome","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 June 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 June 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ciac2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/easyconferences.eu\/ciac2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}