{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:23Z","timestamp":1740122423949,"version":"3.37.3"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2019,3,18]],"date-time":"2019-03-18T00:00:00Z","timestamp":1552867200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100013000","name":"Politecnico di Torino","doi-asserted-by":"publisher","award":["TESUN-83486178370409"],"award-info":[{"award-number":["TESUN-83486178370409"]}],"id":[{"id":"10.13039\/100013000","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2019,8]]},"DOI":"10.1007\/s10878-019-00399-w","type":"journal-article","created":{"date-parts":[[2019,3,18]],"date-time":"2019-03-18T06:02:52Z","timestamp":1552888972000},"page":"608-617","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A tight linear time \n                \n                  \n                \n                $$\\frac{13}{12}$$\n                \n                  \n                    \n                      13\n                      12\n                    \n                  \n                \n              -approximation algorithm for the \n                \n                  \n                \n                $$P2 || C_{\\max }$$\n                \n                  \n                    \n                      \n                        P\n                        2\n                        |\n                        |\n                      \n                      \n                        C\n                        max\n                      \n                    \n                  \n                \n               problem"],"prefix":"10.1007","volume":"38","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2897-183X","authenticated-orcid":false,"given":"Federico","family":"Della Croce","sequence":"first","affiliation":[]},{"given":"Rosario","family":"Scatamacchia","sequence":"additional","affiliation":[]},{"given":"Vincent","family":"T\u2019kindt","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,3,18]]},"reference":[{"key":"#cr-split#-399_CR1.1","unstructured":"Abolhassani M, Chan HT-H, Chen F, Esfandiari H, Hajiaghayi M, Hamid M, Wu X (2016) Beating ratio 0.5 for weighted oblivious matching problems. In: Sankowski P, Zaroliagis C"},{"key":"#cr-split#-399_CR1.2","unstructured":"(ed) 24th annual European symposium on algorithms (ESA 2016), vol 57, pp 3:1-3:18. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik"},{"key":"399_CR2","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1002\/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J","volume":"1","author":"N Alon","year":"1998","unstructured":"Alon N, Azar Y, Woeginger GJ, Yadid Y (1998) Approximation schemes for scheduling on parallel machines. J Sched 1:55\u201366","journal-title":"J Sched"},{"key":"399_CR3","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/s10951-015-0419-z","volume":"18","author":"JD Blocher","year":"2015","unstructured":"Blocher JD, Sevastyanov D (2015) A note on the Coffman-Sethi bound for LPT scheduling. J Sched 18:325\u2013327","journal-title":"J Sched"},{"key":"399_CR4","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M Blum","year":"1973","unstructured":"Blum M, Floyd RW, Pratt V, Rivest RL, Tarjan RE (1973) Time bounds for selection. J Comput Syst Sci 7:448\u2013461","journal-title":"J Comput Syst Sci"},{"key":"399_CR5","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/0167-6377(93)90024-B","volume":"14","author":"B Chen","year":"1993","unstructured":"Chen B (1993) A note on LPT scheduling. Oper Res Lett 14:139\u2013142","journal-title":"Oper Res Lett"},{"key":"399_CR6","unstructured":"Chimani M, Wiedera T (2016) An ILP-based proof system for the crossing number problem. In: Sankowski P, Zaroliagis C (eds) 24th annual European symposium on algorithms (ESA 2016), vol 57, pp 29:1\u201329:13. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik"},{"key":"399_CR7","first-page":"17","volume":"10","author":"EG Coffman Jr","year":"1976","unstructured":"Coffman EG Jr, Sethi R (1976) A generalized bound on LPT sequencing. Rev Fr d\u2019Automatique Inform Rech Oper Suppl 10:17\u201325","journal-title":"Rev Fr d\u2019Automatique Inform Rech Oper Suppl"},{"key":"399_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0207001","volume":"7","author":"EG Coffman Jr","year":"1978","unstructured":"Coffman EG Jr, Garey MR, Johnson DS (1978) An application of bin-packing to multiprocessor scheduling. SIAM J Comput 7:1\u201317","journal-title":"SIAM J Comput"},{"key":"399_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-018-0597-6","author":"F Della Croce","year":"2018","unstructured":"Della Croce F, Scatamacchia R (2018) The longest processing time rule for identical parallel machines revisited. J Sched. \n                    https:\/\/doi.org\/10.1007\/s10951-018-0597-6","journal-title":"J Sched"},{"key":"399_CR10","doi-asserted-by":"crossref","unstructured":"Della Croce F., Pferschy U., Scatamacchia R. (2018) Approximation results for the incremental knapsack problem. In: Combinatorial algorithms: 28th international workshop, IWOCA 2017, vol 10765 of Springer lecture notes in computer science, pp 75\u201387","DOI":"10.1007\/978-3-319-78825-8_7"},{"key":"399_CR11","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"RL Graham","year":"1969","unstructured":"Graham RL (1969) Bounds on multiprocessors timing anomalies. SIAM J Appl Math 17:416\u2013429","journal-title":"SIAM J Appl Math"},{"key":"399_CR12","doi-asserted-by":"crossref","unstructured":"Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discrete Math 5(C):287\u2013326","DOI":"10.1016\/S0167-5060(08)70356-X"},{"issue":"1","key":"399_CR13","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1080\/09537280150203951","volume":"12","author":"JND Gupta","year":"2001","unstructured":"Gupta JND, Ruiz-Torres AJ (2001) A listfit heuristic for minimizing makespan on identical parallel machines. Prod Plan Control 12(1):28\u201336","journal-title":"Prod Plan Control"},{"key":"399_CR14","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1002\/1520-6750(200010)47:7<593::AID-NAV4>3.0.CO;2-H","volume":"47","author":"Y He","year":"2000","unstructured":"He Y, Kellerer H, Koto V (2000) Linear compound algorithms for the partitioning problems. Nav Res Logist 47:593\u2013601","journal-title":"Nav Res Logist"},{"volume-title":"Approximation algorithms for NP-hard problems","year":"1997","key":"399_CR15","unstructured":"Hochbaum DS (ed) (1997) Approximation algorithms for NP-hard problems. PWS Publishing Co., Boston"},{"key":"399_CR16","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"DS Hochbaum","year":"1987","unstructured":"Hochbaum DS, Shmoys DB (1987) Using dual approximation algorithms for scheduling problems theoretical and practical results. J ACM 34:144\u2013162","journal-title":"J ACM"},{"key":"399_CR17","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1137\/090749451","volume":"24","author":"K Jansen","year":"2010","unstructured":"Jansen K (2010) An eptas for scheduling jobs on uniform processors: using an milp relaxation with a constant number of integral variables. SIAM J Discrete Math 24:457\u2013485","journal-title":"SIAM J Discrete Math"},{"key":"399_CR18","unstructured":"Jansen K, Klein KM, Verschae J (2017) Improved efficient approximation schemes for scheduling jobs on identical and uniform machines. In: Proceedings of the 13th workshop on models and algorithms for planning and scheduling problems (MAPSP 2017), Seeon Abbey, Germany"},{"key":"399_CR19","doi-asserted-by":"publisher","first-page":"660","DOI":"10.1016\/j.ejor.2007.04.013","volume":"187","author":"C Koulamas","year":"2008","unstructured":"Koulamas C, Kyparisis GJ (2008) An improved delayed-start LPT algorithm for a partition problem on two identical parallel machines. Eur J Oper Res 187:660\u2013666","journal-title":"Eur J Oper Res"},{"issue":"3","key":"399_CR20","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0166-218X(88)90079-0","volume":"20","author":"CY Lee","year":"1988","unstructured":"Lee CY, Massey JD (1988) Multiprocessor scheduling: combining LPT and MULTIFIT. Discrete Appl Math 20(3):233\u2013242","journal-title":"Discrete Appl Math"},{"issue":"1","key":"399_CR21","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1287\/opre.45.1.116","volume":"45","author":"P Mireault","year":"1997","unstructured":"Mireault P, Orlin JB, Vohra RV (1997) A parametric worst-case analysis of the LPT heuristic for two uniform machines. Oper Res 45(1):116\u2013125","journal-title":"Oper Res"},{"key":"399_CR22","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1145\/321921.321934","volume":"23","author":"S Sahni","year":"1976","unstructured":"Sahni S (1976) Algorithms for scheduling independent tasks. J ACM 23:116\u2013127","journal-title":"J ACM"},{"key":"399_CR23","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/s10100-015-0429-0","volume":"25","author":"R Walter","year":"2017","unstructured":"Walter R (2017) A note on minimizing the sum of squares of machine completion times on two identical parallel machines. Cent Eur J Oper Res 25:139\u2013144","journal-title":"Cent Eur J Oper Res"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-019-00399-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-019-00399-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-019-00399-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,17]],"date-time":"2020-03-17T00:15:19Z","timestamp":1584404119000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-019-00399-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,18]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,8]]}},"alternative-id":["399"],"URL":"https:\/\/doi.org\/10.1007\/s10878-019-00399-w","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2019,3,18]]},"assertion":[{"value":"18 March 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}