{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,28]],"date-time":"2025-02-28T17:10:17Z","timestamp":1740762617739,"version":"3.38.0"},"reference-count":53,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2024,7,22]],"date-time":"2024-07-22T00:00:00Z","timestamp":1721606400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,7,22]],"date-time":"2024-07-22T00:00:00Z","timestamp":1721606400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["EXC-2046\/1","EXC-2046\/1","EXC-2046\/1"],"award-info":[{"award-number":["EXC-2046\/1","EXC-2046\/1","EXC-2046\/1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2025,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>We study kill-and-restart and preemptive strategies for the fundamental scheduling problem of minimizing the sum of weighted completion times on a single machine in the non-clairvoyant setting. First, we show a lower bound of\u00a03 for any deterministic non-clairvoyant kill-and-restart strategy. Then, we give for any <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$b &gt; 1$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>b<\/mml:mi>\n                    <mml:mo>&gt;<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> a tight analysis for the natural <jats:italic>b<\/jats:italic>-scaling kill-and-restart strategy as well as for a randomized variant of it. In particular, we show a competitive ratio of <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$(1+3\\sqrt{3})\\approx 6.197$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mn>3<\/mml:mn>\n                    <mml:msqrt>\n                      <mml:mn>3<\/mml:mn>\n                    <\/mml:msqrt>\n                    <mml:mo>)<\/mml:mo>\n                    <mml:mo>\u2248<\/mml:mo>\n                    <mml:mn>6.197<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> for the deterministic and of <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\approx 3.032$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>\u2248<\/mml:mo>\n                    <mml:mn>3.032<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> for the randomized strategy, by making use of the largest eigenvalue of a Toeplitz matrix. In addition, we show that the preemptive Weighted Shortest Elapsed Time First (WSETF) rule is 2-competitive when jobs are released online, matching the lower bound for the unit weight case with trivial release dates for any non-clairvoyant algorithm. Using this result as well as the competitiveness of round-robin for multiple machines, we prove performance guarantees smaller than 10 for adaptions of the <jats:italic>b<\/jats:italic>-scaling strategy to online release dates and unweighted jobs on identical parallel machines.<\/jats:p>","DOI":"10.1007\/s10107-024-02118-8","type":"journal-article","created":{"date-parts":[[2024,7,22]],"date-time":"2024-07-22T08:01:46Z","timestamp":1721635306000},"page":"457-509","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Competitive kill-and-restart and preemptive strategies for non-clairvoyant scheduling"],"prefix":"10.1007","volume":"210","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7003-1430","authenticated-orcid":false,"given":"Sven","family":"J\u00e4ger","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6910-8907","authenticated-orcid":false,"given":"Guillaume","family":"Sagnol","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9331-445X","authenticated-orcid":false,"given":"Daniel","family":"Schmidt\u00a0genannt\u00a0Waldschmidt","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2878-6872","authenticated-orcid":false,"given":"Philipp","family":"Warode","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,7,22]]},"reference":[{"key":"2118_CR1","doi-asserted-by":"publisher","unstructured":"J\u00e4ger, S., Sagnol, G., Schmidt genannt Waldschmidt, D., Warode, P.: Competitive kill-and-restart and preemptive strategies for non-clairvoyant scheduling. In: Del\u00a0Pia, A., Kaibel, V. (eds.) Integer Program. Combin. Optim. (IPCO). LNCS, vol. 13904, pp. 246\u2013260. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-32726-1_18","DOI":"10.1007\/978-3-031-32726-1_18"},{"issue":"1\u20132","key":"2118_CR2","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"WE Smith","year":"1956","unstructured":"Smith, W.E.: Various optimizers for single-stage production. Nav. Res. Logist. Q. 3(1\u20132), 59\u201366 (1956). https:\/\/doi.org\/10.1002\/nav.3800030106","journal-title":"Nav. Res. Logist. Q."},{"issue":"1","key":"2118_CR3","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0304-3975(94)90152-X","volume":"130","author":"A Feldmann","year":"1994","unstructured":"Feldmann, A., Sgall, J., Teng, S.-H.: Dynamic scheduling on parallel machines. Theor. Comput. Sci. 130(1), 49\u201372 (1994). https:\/\/doi.org\/10.1016\/0304-3975(94)90152-X","journal-title":"Theor. Comput. Sci."},{"issue":"6","key":"2118_CR4","doi-asserted-by":"publisher","first-page":"1313","DOI":"10.1137\/S0097539793248317","volume":"24","author":"DB Shmoys","year":"1995","unstructured":"Shmoys, D.B., Wein, J., Williamson, D.P.: Scheduling parallel machines on-line. SIAM J. Comput. 24(6), 1313\u20131331 (1995). https:\/\/doi.org\/10.1137\/S0097539793248317","journal-title":"SIAM J. Comput."},{"issue":"1","key":"2118_CR5","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0304-3975(94)90151-1","volume":"130","author":"R Motwani","year":"1994","unstructured":"Motwani, R., Phillips, S., Torng, E.: Nonclairvoyant scheduling. Theor. Comput. Sci. 130(1), 17\u201347 (1994). https:\/\/doi.org\/10.1016\/0304-3975(94)90151-1","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"2118_CR6","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/S0020-0190(03)00231-X","volume":"87","author":"J Kim","year":"2003","unstructured":"Kim, J., Chwa, K.: Non-clairvoyant scheduling for weighted flow time. Inf. Process. Lett. 87(1), 31\u201337 (2003). https:\/\/doi.org\/10.1016\/S0020-0190(03)00231-X","journal-title":"Inf. Process. Lett."},{"key":"2118_CR7","doi-asserted-by":"publisher","unstructured":"Beaumont, O., Bonichon, N., Eyraud-Dubois, L., Marchal, L.: Minimizing weighted mean completion time for malleable tasks scheduling. In: Oliker, L., Yelick, K. (eds.) 26th IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 273\u2013284 (2012). https:\/\/doi.org\/10.1109\/ipdps.2012.34","DOI":"10.1109\/ipdps.2012.34"},{"issue":"1","key":"2118_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3136754","volume":"65","author":"S Im","year":"2017","unstructured":"Im, S., Kulkarni, J., Munagala, K.: Competitive algorithms from competitive equilibria: non-clairvoyant scheduling under polyhedral constraints. J. ACM 65(1), 1\u201333 (2017). https:\/\/doi.org\/10.1145\/3136754","journal-title":"J. ACM"},{"key":"2118_CR9","doi-asserted-by":"publisher","unstructured":"Im, S., Kulkarni, J., Munagala, K., Pruhs, K.: SelfishMigrate: A scalable algorithm for non-clairvoyantly scheduling heterogeneous processors. In: Barak, B. (ed.) 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 531\u2013540 (2014). https:\/\/doi.org\/10.1109\/FOCS.2014.63","DOI":"10.1109\/FOCS.2014.63"},{"key":"2118_CR10","doi-asserted-by":"publisher","unstructured":"Garg, N., Gupta, A., Kumar, A., Singla, S.: Non-clairvoyant precedence constrained scheduling. In: Baier, C., Chatzigiannakis, I., Flocchini, P., Leonardi, S. (eds.) 46th International Colloquium on Automata, Languages and Programming (ICALP). LIPIcs, vol. 132, pp. 63:1\u201363:14. Dagstuhl (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.63","DOI":"10.4230\/LIPIcs.ICALP.2019.63"},{"key":"2118_CR11","unstructured":"Lassota, A.A., Lindermayr, A., Megow, N., Schl\u00f6ter, J.: Minimalistic predictions to schedule jobs with online precedence constraints. In: Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., Scarlett, J. (eds.) Proceeding of 40th International Conference on Machine Learning, PMLR, vol. 202, pp. 18563\u201318583. https:\/\/proceedings.mlr.press\/v202\/lassota23a.html"},{"key":"2118_CR12","doi-asserted-by":"publisher","unstructured":"Lindermayr, A., Megow, N.: Permutation predictions for non-clairvoyant scheduling. In: Lee, I.-T.A. (ed.) Proceeding of 34th Symposium on Parallel Algorithms Architecture (SPAA), pp. 357\u2013368. ACM, New York, NY (2022). https:\/\/doi.org\/10.1145\/3490148.3538579","DOI":"10.1145\/3490148.3538579"},{"issue":"4","key":"2118_CR13","doi-asserted-by":"publisher","first-page":"1297","DOI":"10.1287\/moor.2014.0653","volume":"39","author":"N Megow","year":"2014","unstructured":"Megow, N., Vredeveld, T.: A tight 2-approximation for preemptive stochastic scheduling. Math. Oper. Res. 39(4), 1297\u20131310 (2014). https:\/\/doi.org\/10.1287\/moor.2014.0653","journal-title":"Math. Oper. Res."},{"issue":"1","key":"2118_CR14","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1145\/321796.321803","volume":"21","author":"KC Sevcik","year":"1974","unstructured":"Sevcik, K.C.: Scheduling for minimum total loss using service time distributions. J. ACM 21(1), 66\u201375 (1974). https:\/\/doi.org\/10.1145\/321796.321803","journal-title":"J. ACM"},{"issue":"3","key":"2118_CR15","doi-asserted-by":"publisher","first-page":"821","DOI":"10.2307\/1428135","volume":"27","author":"G Weiss","year":"1995","unstructured":"Weiss, G.: On almost optimal priority rules for preemptive scheduling of stochastic jobs on parallel machines. Adv. Appl. Probab. 27(3), 821\u2013839 (1995). https:\/\/doi.org\/10.2307\/1428135","journal-title":"Adv. Appl. Probab."},{"issue":"9","key":"2118_CR16","doi-asserted-by":"publisher","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"RL Graham","year":"1966","unstructured":"Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45(9), 1563\u20131581 (1966). https:\/\/doi.org\/10.1002\/j.1538-7305.1966.tb01709.x","journal-title":"Bell Syst. Tech. J."},{"key":"2118_CR17","volume-title":"Theory of Scheduling","author":"RW Conway","year":"1967","unstructured":"Conway, R.W., Maxwell, W.L., Miller, L.W.: Theory of Scheduling. Addison-Wesley, Reading, Palo Alto, London, Don Mills (1967)"},{"key":"2118_CR18","doi-asserted-by":"publisher","unstructured":"Rinnooy\u00a0Kan, A.H.G.: Machine Scheduling Problems: Classification, Complexity and Computations. Martinus Nijhoff, Den Haag (1976). https:\/\/doi.org\/10.1007\/978-1-4613-4383-7","DOI":"10.1007\/978-1-4613-4383-7"},{"key":"2118_CR19","doi-asserted-by":"publisher","unstructured":"Afrati, F., Bampis, E., Chekuri, C., Karger, D., Kenyon, C., Khanna, S., Milis, I., Queyranne, M., Skutella, M., Stein, C., Sviridenko, M.: Approximation schemes for minimizing average weighted completion time with release dates. In: 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 32\u201343 (1999). https:\/\/doi.org\/10.1109\/SFFCS.1999.814574","DOI":"10.1109\/SFFCS.1999.814574"},{"key":"2118_CR20","doi-asserted-by":"publisher","unstructured":"Hoogeveen, J.A., Vestjens, A.P.A.: Optimal on-line algorithms for single-machine scheduling. In: Cunningham, W.H., McCormick, S.T., Queyranne, M. (eds.) Integer Programming Combined Optimization (IPCO). LNCS, vol. 1084, pp. 404\u2013414. Springer, Berlin, Heidelberg (1996). https:\/\/doi.org\/10.1007\/3-540-61310-2_30","DOI":"10.1007\/3-540-61310-2_30"},{"issue":"3","key":"2118_CR21","doi-asserted-by":"publisher","first-page":"686","DOI":"10.1287\/moor.1040.0092","volume":"29","author":"EJ Anderson","year":"2004","unstructured":"Anderson, E.J., Potts, C.N.: Online scheduling of a single machine to minimize total weighted completion time. Math. Oper. Res. 29(3), 686\u2013697 (2004). https:\/\/doi.org\/10.1287\/moor.1040.0092","journal-title":"Math. Oper. Res."},{"issue":"7","key":"2118_CR22","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/BF01919323","volume":"28","author":"RH M\u00f6hring","year":"1984","unstructured":"M\u00f6hring, R.H., Radermacher, F.J., Weiss, G.: Stochastic scheduling problems I - general strategies. Z. Oper. Res. 28(7), 193\u2013260 (1984). https:\/\/doi.org\/10.1007\/BF01919323","journal-title":"Z. Oper. Res."},{"issue":"1","key":"2118_CR23","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1145\/1120582.1120585","volume":"53","author":"M Scharbrodt","year":"2006","unstructured":"Scharbrodt, M., Schickinger, T., Steger, A.: A new average case analysis for completion time scheduling. J. ACM 53(1), 121\u2013146 (2006). https:\/\/doi.org\/10.1145\/1120582.1120585","journal-title":"J. ACM"},{"issue":"9","key":"2118_CR24","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1287\/mnsc.12.9.707","volume":"12","author":"MH Rothkopf","year":"1966","unstructured":"Rothkopf, M.H.: Scheduling with random service times. Manag. Sci. 12(9), 707\u2013713 (1966). https:\/\/doi.org\/10.1287\/mnsc.12.9.707","journal-title":"Manag. Sci."},{"issue":"6","key":"2118_CR25","doi-asserted-by":"publisher","first-page":"924","DOI":"10.1145\/331524.331530","volume":"46","author":"RH M\u00f6hring","year":"1999","unstructured":"M\u00f6hring, R.H., Schulz, A.S., Uetz, M.: Approximation in stochastic scheduling: the power of LP-based priority policies. J. ACM 46(6), 924\u2013942 (1999). https:\/\/doi.org\/10.1145\/331524.331530","journal-title":"J. ACM"},{"key":"2118_CR26","doi-asserted-by":"publisher","unstructured":"J\u00e4ger, S.J.: Approximation in deterministic and stochastic machine scheduling. PhD thesis, Technische Universit\u00e4t Berlin (2021). https:\/\/doi.org\/10.14279\/depositonce-12198","DOI":"10.14279\/depositonce-12198"},{"key":"2118_CR27","doi-asserted-by":"publisher","unstructured":"J\u00e4ger, S., Skutella, M.: Generalizing the Kawaguchi-Kyan bound to stochastic parallel machine scheduling. In: Niedermeier, R., Vall\u00e9e, B. (eds.) 35th International Symposium on Theoretical Aspects of Computer Science (STACS). LIPIcs, vol. 96, pp. 43:1\u201343:13. Dagstuhl (2018). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2018.43","DOI":"10.4230\/LIPIcs.STACS.2018.43"},{"key":"2118_CR28","doi-asserted-by":"publisher","unstructured":"Im, S., Moseley, B., Pruhs, K.: Stochastic scheduling of heavy-tailed jobs. In: Mayr, E.W., Ollinger, N. (eds.) 32nd International Symposium on Theoretical Aspects of Computer Science (STACS). LIPIcs, vol. 30, pp. 474\u2013486. Dagstuhl (2015). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2015.474","DOI":"10.4230\/LIPIcs.STACS.2015.474"},{"issue":"1","key":"2118_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/mnsc.6.1.1","volume":"6","author":"R McNaughton","year":"1959","unstructured":"McNaughton, R.: Scheduling with deadlines and loss functions. Manag. Sci. 6(1), 1\u201312 (1959). https:\/\/doi.org\/10.1287\/mnsc.6.1.1","journal-title":"Manag. Sci."},{"issue":"6","key":"2118_CR30","doi-asserted-by":"publisher","first-page":"772","DOI":"10.1016\/j.orl.2016.09.013","volume":"44","author":"L Epstein","year":"2016","unstructured":"Epstein, L., Levin, A.: The benefit of preemption for single machine scheduling so as to minimize total weighted completion time. Oper. Res. Lett. 44(6), 772\u2013774 (2016). https:\/\/doi.org\/10.1016\/j.orl.2016.09.013","journal-title":"Oper. Res. Lett."},{"key":"2118_CR31","doi-asserted-by":"publisher","unstructured":"Labetoulle, J., Lawler, E.L., Lenstra, J.K., Rinnooy\u00a0Kan, A.H.G.: Preemptive scheduling of uniform machines subject to release dates. In: Pulleyblank, W.R. (ed.) Progress in Combinatorial Optimization, pp. 245\u2013261. Academic Press, Don Mills, ON (1984). https:\/\/doi.org\/10.1016\/B978-0-12-566780-7.50020-9","DOI":"10.1016\/B978-0-12-566780-7.50020-9"},{"issue":"6","key":"2118_CR32","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1016\/j.orl.2010.08.012","volume":"38","author":"R Sitters","year":"2010","unstructured":"Sitters, R.: Competitive analysis of preemptive single-machine scheduling. Oper. Res. Lett. 38(6), 585\u2013588 (2010). https:\/\/doi.org\/10.1016\/j.orl.2010.08.012","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"2118_CR33","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1016\/S0304-3975(02)00488-7","volume":"299","author":"L Epstein","year":"2003","unstructured":"Epstein, L., van Stee, R.: Lower bounds for on-line single-machine scheduling. Theor. Comput. Sci. 299(1), 439\u2013450 (2003). https:\/\/doi.org\/10.1016\/S0304-3975(02)00488-7","journal-title":"Theor. Comput. Sci."},{"key":"2118_CR34","unstructured":"Parekh, A.K.J.: A generalized processor sharing approach to flow control in integrated services networks. PhD thesis, Massachusetts Institute of Technology (1992). https:\/\/dspace.mit.edu\/handle\/1721.1\/13076"},{"key":"2118_CR35","unstructured":"Chandra, A., Adler, M., Goyal, P., Shenoy, P.: Surplus fair scheduling: A proportional-share CPU scheduling algorithm for symmetric multiprocessors. In: 4th Symposium on Operating Systems Design and Implementation (OSDI), pp. 4:1\u20134:14. USENIX, Berkeley, CA (2000). https:\/\/www.usenix.org\/conference\/osdi-2000\/surplus-fair-scheduling-proportional-share-cpu-scheduling-algorithm-symmetric"},{"issue":"4","key":"2118_CR36","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1145\/1008731.1008732","volume":"51","author":"L Becchetti","year":"2004","unstructured":"Becchetti, L., Leonardi, S.: Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines. J. ACM 51(4), 517\u2013539 (2004). https:\/\/doi.org\/10.1145\/1008731.1008732","journal-title":"J. ACM"},{"issue":"4","key":"2118_CR37","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1145\/347476.347479","volume":"47","author":"B Kalyanasundaram","year":"2000","unstructured":"Kalyanasundaram, B., Pruhs, K.: Speed is as powerful as clairvoyance. J. ACM 47(4), 617\u2013643 (2000). https:\/\/doi.org\/10.1145\/347476.347479","journal-title":"J. ACM"},{"issue":"4","key":"2118_CR38","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1145\/1290672.1290676","volume":"3","author":"N Bansal","year":"2007","unstructured":"Bansal, N., Dhamdhere, K.: Minimizing weighted flow time. ACM Trans. Algor. 3(4), 39\u201313914 (2007). https:\/\/doi.org\/10.1145\/1290672.1290676","journal-title":"ACM Trans. Algor."},{"key":"2118_CR39","doi-asserted-by":"publisher","unstructured":"Bansal, N., Pruhs, K.: Server scheduling in the weighted $$\\ell _p$$-norm. In: Farach-Colton, M. (ed.) Theor. Inform. (LATIN). LNCS, vol. 2976, pp. 434\u2013443. Springer, Berlin, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-24698-5_47","DOI":"10.1007\/978-3-540-24698-5_47"},{"key":"2118_CR40","doi-asserted-by":"publisher","unstructured":"Vestjens, A.P.A.: On-line machine scheduling. PhD thesis, Technische Universiteit Eindhoven (November 1997).https:\/\/doi.org\/10.6100\/IR500043","DOI":"10.6100\/IR500043"},{"issue":"2","key":"2118_CR41","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/j.jalgor.2004.10.001","volume":"57","author":"R Stee","year":"2005","unstructured":"Stee, R., La Poutr\u00e9, H.: Minimizing the total completion time on-line on a single machine, using restarts. J. Algor. 57(2), 95\u2013129 (2005). https:\/\/doi.org\/10.1016\/j.jalgor.2004.10.001","journal-title":"J. Algor."},{"issue":"1","key":"2118_CR42","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/S0097539797327180","volume":"31","author":"C Chekuri","year":"2001","unstructured":"Chekuri, C., Motwani, R., Natarajan, B., Stein, C.: Approximation techniques for average completion time scheduling. SIAM J. Comput. 31(1), 146\u2013166 (2001). https:\/\/doi.org\/10.1137\/S0097539797327180","journal-title":"SIAM J. Comput."},{"issue":"12","key":"2118_CR43","doi-asserted-by":"publisher","first-page":"3630","DOI":"10.1007\/s00453-020-00742-2","volume":"82","author":"C D\u00fcrr","year":"2020","unstructured":"D\u00fcrr, C., Erlebach, T., Megow, N., Mei\u00dfner, J.: An adversarial model for scheduling with testing. Algorithmica 82(12), 3630\u20133675 (2020). https:\/\/doi.org\/10.1007\/s00453-020-00742-2","journal-title":"Algorithmica"},{"key":"2118_CR44","doi-asserted-by":"publisher","unstructured":"Albers, S., Eckl, A.: Explorable uncertainty in scheduling with non-uniform testing times. In: Kaklamanis, C., Levin, A. (eds.) Approximation and Online Algorithms (WAOA). LNCS, vol. 12806, pp. 127\u2013142. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-80879-2_9","DOI":"10.1007\/978-3-030-80879-2_9"},{"key":"2118_CR45","doi-asserted-by":"publisher","unstructured":"Gong, M., Lin, G.: Improved approximation algorithms for multiprocessor scheduling with testing. In: Chen, J., Li, M., Zhang, G. (eds.) Frontiers Algorithmics (IJTCS-FAW). LNCS, vol. 12874, pp. 65\u201377. Springer, Cham (2021).https:\/\/doi.org\/10.1007\/978-3-030-97099-4_5","DOI":"10.1007\/978-3-030-97099-4_5"},{"issue":"2","key":"2118_CR46","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1006\/inco.1993.1054","volume":"106","author":"RA Baeza-Yates","year":"1993","unstructured":"Baeza-Yates, R.A., Culberson, J.C., Rawlins, G.J.E.: Searching in the plane. Inf. Comput. 106(2), 234\u2013252 (1993). https:\/\/doi.org\/10.1006\/inco.1993.1054","journal-title":"Inf. Comput."},{"issue":"4","key":"2118_CR47","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/BF02798690","volume":"8","author":"A Beck","year":"1970","unstructured":"Beck, A., Newman, D.J.: Yet more on the linear search problem. Israel J. Math. 8(4), 419\u2013429 (1970). https:\/\/doi.org\/10.1007\/BF02798690","journal-title":"Israel J. Math."},{"issue":"1","key":"2118_CR48","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1006\/inco.1996.0092","volume":"131","author":"M-Y Kao","year":"1996","unstructured":"Kao, M.-Y., Reif, J.H., Tate, S.R.: Searching in an unknown environment: an optimal randomized algorithm for the cow-path problem. Inf. Comput. 131(1), 63\u201379 (1996). https:\/\/doi.org\/10.1006\/inco.1996.0092","journal-title":"Inf. Comput."},{"issue":"1","key":"2118_CR49","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1006\/jagm.1998.0959","volume":"29","author":"M-Y Kao","year":"1998","unstructured":"Kao, M.-Y., Ma, Y., Sipser, M., Yin, Y.: Optimal constructions of hybrid algorithms. J. Alg. 29(1), 142\u2013164 (1998). https:\/\/doi.org\/10.1006\/jagm.1998.0959","journal-title":"J. Alg."},{"key":"2118_CR50","doi-asserted-by":"publisher","unstructured":"Yao, A.C.-C.: Probabilistic computations: Toward a unified measure of complexity. In: 18th Annual IEEE Symposium on Foundations of Computer Science (SFCS), pp. 222\u2013227 (1977). https:\/\/doi.org\/10.1109\/SFCS.1977.24","DOI":"10.1109\/SFCS.1977.24"},{"key":"2118_CR51","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898717853","volume-title":"Spectral Properties of Banded Toeplitz Matrices","author":"A B\u00f6ttcher","year":"2005","unstructured":"B\u00f6ttcher, A., Grudsky, S.M.: Spectral Properties of Banded Toeplitz Matrices. SIAM, Philadelphia, PA (2005)"},{"key":"2118_CR52","doi-asserted-by":"publisher","unstructured":"Goemans, M.X.: A supermodular relaxation for scheduling with release dates. In: Cunningham, W.H., McCormick, S.T., Queyranne, M. (eds.) Integer Programming and Combinatorial Optimization. LNCS, vol. 1084, pp. 288\u2013300. Springer, Berlin, Heidelberg (1996). https:\/\/doi.org\/10.1007\/3-540-61310-2_22","DOI":"10.1007\/3-540-61310-2_22"},{"key":"2118_CR53","doi-asserted-by":"publisher","unstructured":"Goemans, M.X.: Improved approximation algorthims for scheduling with release dates. In: Saks, M. (ed.) Proceeding of Eighth Annual of ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 591\u2013598 (1997).https:\/\/doi.org\/10.5555\/314161.314394","DOI":"10.5555\/314161.314394"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02118-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-024-02118-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02118-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,28]],"date-time":"2025-02-28T16:00:56Z","timestamp":1740758456000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-024-02118-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,22]]},"references-count":53,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["2118"],"URL":"https:\/\/doi.org\/10.1007\/s10107-024-02118-8","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2024,7,22]]},"assertion":[{"value":"3 August 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 June 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 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":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}}]}}