{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,22]],"date-time":"2026-03-22T21:46:36Z","timestamp":1774215996130,"version":"3.50.1"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2022,5,7]],"date-time":"2022-05-07T00:00:00Z","timestamp":1651881600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,5,7]],"date-time":"2022-05-07T00:00:00Z","timestamp":1651881600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["617951"],"award-info":[{"award-number":["617951"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["853234"],"award-info":[{"award-number":["853234"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["024.002.003"],"award-info":[{"award-number":["024.002.003"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["613.009.031b"],"award-info":[{"award-number":["613.009.031b"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["617951"],"award-info":[{"award-number":["617951"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study a natural variant of scheduling that we call <jats:italic>partial scheduling<\/jats:italic>: in this variant an instance of a scheduling problem along with an integer\u00a0<jats:italic>k<\/jats:italic> is given and one seeks an optimal schedule where not all, but only <jats:italic>k<\/jats:italic> jobs, have to be processed. Specifically, we aim to determine the fine-grained parameterized complexity of partial scheduling problems parameterized by <jats:italic>k<\/jats:italic> for all variants of scheduling problems that minimize the makespan and involve unit\/arbitrary processing times, identical\/unrelated parallel machines, release\/due dates, and precedence constraints. That is, we investigate whether algorithms with runtimes of the type <jats:inline-formula><jats:alternatives><jats:tex-math>$$f(k)n^{{\\mathcal {O}}(1)}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>f<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>k<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mrow>\n                        <mml:mi>O<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mn>1<\/mml:mn>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:msup>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> or <jats:inline-formula><jats:alternatives><jats:tex-math>$$n^{{\\mathcal {O}}(f(k))}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mi>O<\/mml:mi>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>f<\/mml:mi>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>k<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> exist for a function <jats:italic>f<\/jats:italic> that is as small as possible. Our contribution is two-fold: First, we categorize each variant to be either in <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathsf {P}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>P<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, <jats:inline-formula><jats:alternatives><jats:tex-math>$${{\\mathsf {N}}}{{\\mathsf {P}}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>N<\/mml:mi>\n                    <mml:mi>P<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-complete and fixed-parameter tractable by <jats:italic>k<\/jats:italic>, or <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathsf {W}}[1]$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>W<\/mml:mi>\n                    <mml:mo>[<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>]<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-hard parameterized by <jats:italic>k<\/jats:italic>. Second, for many interesting cases we further investigate the runtime on a finer scale and obtain run times that are (almost) optimal assuming the Exponential Time Hypothesis. As one of our main technical contributions, we give an <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathcal {O}}(8^kk(|V|+|E|))$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mrow>\n                      <mml:mi>O<\/mml:mi>\n                      <mml:mo>(<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:msup>\n                      <mml:mn>8<\/mml:mn>\n                      <mml:mi>k<\/mml:mi>\n                    <\/mml:msup>\n                    <mml:mrow>\n                      <mml:mi>k<\/mml:mi>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mo>|<\/mml:mo>\n                      <mml:mi>V<\/mml:mi>\n                      <mml:mo>|<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mrow>\n                      <mml:mo>|<\/mml:mo>\n                      <mml:mi>E<\/mml:mi>\n                      <mml:mo>|<\/mml:mo>\n                      <mml:mo>)<\/mml:mo>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time algorithm to solve instances of partial scheduling problems minimizing the makespan with unit length jobs, precedence constraints and release dates, where <jats:inline-formula><jats:alternatives><jats:tex-math>$$G=(V,E)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>G<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>V<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>E<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the graph with precedence constraints.\n<\/jats:p>","DOI":"10.1007\/s00453-022-00970-8","type":"journal-article","created":{"date-parts":[[2022,5,7]],"date-time":"2022-05-07T07:03:40Z","timestamp":1651907020000},"page":"2309-2334","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the Fine-grained Parameterized Complexity of Partial Scheduling to Minimize the Makespan"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1848-0076","authenticated-orcid":false,"given":"Jesper","family":"Nederlof","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9654-8094","authenticated-orcid":false,"given":"C\u00e9line M. F.","family":"Swennenhuis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,5,7]]},"reference":[{"issue":"4","key":"970_CR1","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844\u2013856 (1995)","journal-title":"J. ACM"},{"issue":"3","key":"970_CR2","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/s10951-018-0581-1","volume":"22","author":"S Bessy","year":"2019","unstructured":"Bessy, S., Giroudeau, R.: Parameterized complexity of a coupled-task scheduling problem. J. Sched. 22(3), 305\u2013313 (2019)","journal-title":"J. Sched."},{"key":"970_CR3","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets M\u00f6bius: fast subset convolution. In: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, pp. 67\u201374. ACM (2007)","DOI":"10.1145\/1250790.1250801"},{"issue":"2","key":"970_CR4","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0167-6377(95)00031-9","volume":"18","author":"HL Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Fellows, M.R.: W[2]-hardness of precedence constrained $$k$$-processor scheduling. Oper. Res. Lett. 18(2), 93\u201397 (1995)","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"970_CR5","doi-asserted-by":"publisher","first-page":"730","DOI":"10.1287\/moor.1060.0218","volume":"31","author":"J Chuzhoy","year":"2006","unstructured":"Chuzhoy, J., Ostrovsky, R., Rabani, Y.: Approximation algorithms for the job interval selection problem and related scheduling problems. Math. Oper. Res. 31(4), 730\u2013738 (2006)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"970_CR6","doi-asserted-by":"publisher","first-page":"692","DOI":"10.1007\/s00453-012-9694-7","volume":"68","author":"M Cygan","year":"2014","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Scheduling partially ordered jobs faster than $$2^n$$. Algorithmica 68(3), 692\u2013714 (2014)","journal-title":"Algorithmica"},{"key":"970_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141, Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms, vol. 3. Springer, Berlin (2015)"},{"issue":"9","key":"970_CR8","doi-asserted-by":"publisher","first-page":"998","DOI":"10.1057\/s41274-017-0238-z","volume":"68","author":"J Eun","year":"2017","unstructured":"Eun, J., Sung, C.S., Kim, E.S.: Maximizing total job value on a single machine with job selection. J. Oper. Res. Soc. 68(9), 998\u20131005 (2017)","journal-title":"J. Oper. Res. Soc."},{"issue":"2","key":"970_CR9","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/S0304-3975(02)00811-3","volume":"298","author":"MR Fellows","year":"2003","unstructured":"Fellows, M.R., McCartin, C.: On the parametric complexity of schedules to minimize tardy tasks. Theoret. Comput. Sci. 298(2), 317\u2013324 (2003)","journal-title":"Theoret. Comput. Sci."},{"key":"970_CR10","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"issue":"2","key":"970_CR11","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"RL Graham","year":"1979","unstructured":"Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discret. Math. 5(2), 287\u2013326 (1979)","journal-title":"Ann. Discret. Math."},{"key":"970_CR12","doi-asserted-by":"publisher","unstructured":"Gupta, A., Krishnaswamy, R., Kumar, A., Segev, D.: Scheduling with outliers. In: Dinur, I., Jansen, K., Naor, J., Rolim, J.D.P. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August 21\u201323, 2009. Proceedings, Lecture Notes in Computer Science, vol. 5687, pp. 149\u2013162. Springer, Berlin (2009). https:\/\/doi.org\/10.1007\/978-3-642-03685-9_12","DOI":"10.1007\/978-3-642-03685-9_12"},{"key":"970_CR13","unstructured":"Hermelin, D., Mnich, M., Omlor, S.: Single machine batch scheduling to minimize the weighted number of tardy jobs. CoRR (2019)"},{"key":"970_CR14","doi-asserted-by":"crossref","unstructured":"Jansen, K., Land, F., Kaluza, M.: Precedence scheduling with unit execution time is equivalent to parametrized biclique. In: International Conference on Current Trends in Theory and Practice of Informatics, pp. 329\u2013343. Springer, Berlin (2016)","DOI":"10.1007\/978-3-662-49192-8_27"},{"issue":"1","key":"970_CR15","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1137\/140952636","volume":"30","author":"K Jansen","year":"2016","unstructured":"Jansen, K., Land, F., Land, K.: Bounding the running time of algorithms for scheduling and packing problems. SIAM J. Discret. Math. 30(1), 343\u2013366 (2016)","journal-title":"SIAM J. Discret. Math."},{"issue":"6","key":"970_CR16","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1002\/nav.21543","volume":"60","author":"C Koulamas","year":"2013","unstructured":"Koulamas, C., Panwalkar, S.S.: A note on combined job selection and sequencing problems. Nav. Res. Logist. 60(6), 449\u2013453 (2013)","journal-title":"Nav. Res. Logist."},{"key":"970_CR17","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/S0167-5060(08)70743-X","volume":"1","author":"JK Lenstra","year":"1977","unstructured":"Lenstra, J.K., Rinnooy Kan, A.H.G., Brucker, P.: Complexity of machine scheduling problems. Ann. Discret. Math. 1, 343\u2013362 (1977)","journal-title":"Ann. Discret. Math."},{"key":"970_CR18","unstructured":"Lent\u00e9, C., Liedloff, M., Soukhal, A., T\u2019Kindt, V.: Exponential algorithms for scheduling problems. Tech. rep. (2014). https:\/\/hal.archives-ouvertes.fr\/hal-00944382"},{"key":"970_CR19","doi-asserted-by":"publisher","first-page":"85","DOI":"10.4086\/toc.2010.v006a005","volume":"6","author":"D Marx","year":"2010","unstructured":"Marx, D.: Can you beat treewidth? Theory Comput. 6, 85\u2013112 (2010)","journal-title":"Theory Comput."},{"key":"970_CR20","unstructured":"Megow, N., Mnich, M., Woeginger, G.: Lorentz Workshop \u2018Scheduling Meets Fixed-Parameter Tractability\u2019 (2019)"},{"key":"970_CR21","doi-asserted-by":"crossref","unstructured":"Mnich, M., van Bevern, R.: Parameterized complexity of machine scheduling: 15 open problems. Comput. Oper. Res. (2018)","DOI":"10.1016\/j.cor.2018.07.020"},{"issue":"1\u20132","key":"970_CR22","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)","journal-title":"Math. Program."},{"issue":"1","key":"970_CR23","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1287\/mnsc.15.1.102","volume":"15","author":"JM Moore","year":"1968","unstructured":"Moore, J.M.: An $$n$$ job, one machine sequencing algorithm for minimizing the number of late jobs. Manag. Sci. 15(1), 102\u2013109 (1968)","journal-title":"Manag. Sci."},{"key":"970_CR24","unstructured":"Pinedo, M.L.: Scheduling: Theory, Algorithms, and Systems, 3rd edn. Springer Publishing Company, Incorporated (2008)"},{"key":"970_CR25","doi-asserted-by":"publisher","unstructured":"Sgall, J.: Open problems in throughput scheduling. In: Epstein, L., Ferragina, P. (eds.) Algorithms\u2014ESA 2012\u201420th Annual European Symposium, Ljubljana, Slovenia, September 10\u201312, 2012. Proceedings, Lecture Notes in Computer Science, vol. 7501, pp. 2\u201311. Springer, Berlin (2012). https:\/\/doi.org\/10.1007\/978-3-642-33090-2_2","DOI":"10.1007\/978-3-642-33090-2_2"},{"issue":"1","key":"970_CR26","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10951-012-0303-z","volume":"16","author":"D Shabtay","year":"2013","unstructured":"Shabtay, D., Gaspar, N., Kaspi, M.: A survey on offline scheduling with rejection. J. Sched. 16(1), 3\u201328 (2013)","journal-title":"J. Sched."},{"issue":"5","key":"970_CR27","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/s10951-014-0398-5","volume":"18","author":"R van Bevern","year":"2015","unstructured":"van Bevern, R., Mnich, M., Niedermeier, R., Weller, M.: Interval scheduling and colorful independent sets. J. Sched. 18(5), 449\u2013469 (2015)","journal-title":"J. Sched."},{"key":"970_CR28","doi-asserted-by":"crossref","unstructured":"van Bevern, R., Bredereck, R., Bulteau, L., Komusiewicz, C., Talmon, N., Woeginger, G.J.: Precedence-constrained scheduling problems parameterized by partial order width. In: Discrete Optimization and Operations Research\u20149th International Conference, DOOR 2016, Vladivostok, Russia, September 19\u201323, 2016, Proceedings, pp. 105\u2013120 (2016)","DOI":"10.1007\/978-3-319-44914-2_9"},{"key":"970_CR29","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithms","author":"DP Williamson","year":"2011","unstructured":"Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, Cambridge (2011)"},{"issue":"3","key":"970_CR30","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1016\/j.cie.2007.02.005","volume":"53","author":"B Yang","year":"2007","unstructured":"Yang, B., Geunes, J.: A single resource scheduling problem with job-selection flexibility, tardiness costs and controllable processing times. Comput. Ind. Eng. 53(3), 420\u2013432 (2007)","journal-title":"Comput. Ind. Eng."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00970-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00970-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00970-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,21]],"date-time":"2022-07-21T13:11:16Z","timestamp":1658409076000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00970-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,7]]},"references-count":30,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["970"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00970-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,7]]},"assertion":[{"value":"19 January 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 April 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 May 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}