{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T19:29:52Z","timestamp":1757618992233,"version":"3.44.0"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T00:00:00Z","timestamp":1748736000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T00:00:00Z","timestamp":1748736000000},"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":["Math Meth Oper Res"],"published-print":{"date-parts":[[2025,6]]},"DOI":"10.1007\/s00186-025-00898-z","type":"journal-article","created":{"date-parts":[[2025,7,15]],"date-time":"2025-07-15T15:45:14Z","timestamp":1752594314000},"page":"507-528","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Sublinear time approximation schemes for makespan minimization on parallel machines"],"prefix":"10.1007","volume":"101","author":[{"given":"Bin","family":"Fu","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3550-8843","authenticated-orcid":false,"given":"Yumei","family":"Huo","sequence":"additional","affiliation":[]},{"given":"Hairong","family":"Zhao","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,7,15]]},"reference":[{"key":"898_CR1","doi-asserted-by":"crossref","unstructured":"Bansal N, Khot S (2009) Optimal long code test with one free bit. In: 50th annual IEEE symposium on foundations of computer science (FOCS), pp 453\u2013462","DOI":"10.1109\/FOCS.2009.23"},{"key":"898_CR2","doi-asserted-by":"publisher","first-page":"627","DOI":"10.1137\/S009753970444572X","volume":"35","author":"B Chazelle","year":"2005","unstructured":"Chazelle B, Liu D, Magen A (2005) Sublinear geometric algorithms. SIAM J Comput 35:627\u2013646","journal-title":"SIAM J Comput"},{"key":"898_CR3","doi-asserted-by":"publisher","first-page":"1370","DOI":"10.1137\/S0097539702403244","volume":"34","author":"B Chazelle","year":"2005","unstructured":"Chazelle B, Rubinfeld R, Trevisan L (2005) Approximating the minimum spanning tree weight in sublinear time. SIAM J Comput 34:1370\u20131379","journal-title":"SIAM J Comput"},{"key":"898_CR4","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1007\/BF00288685","volume":"1","author":"E Coffman","year":"1972","unstructured":"Coffman E, Graham R (1972) Optimal scheduling for two-processor systems. Acta Informatica 1:200\u2013213","journal-title":"Acta Informatica"},{"key":"898_CR5","doi-asserted-by":"crossref","unstructured":"Czumaj A, Sohler C (2004) Estimating the weight of metric minimum spanning trees in sublinear-time. [Venue missing]","DOI":"10.1145\/1007352.1007386"},{"key":"898_CR6","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1137\/S0097539703435297","volume":"35","author":"A Czumaj","year":"2005","unstructured":"Czumaj A, Erg\u00fcn F, Fortnow L, Magen A, Newman I, Rubinfeld R, Sohler C (2005) Approximating the weight of the Euclidean minimum spanning tree in sublinear time. SIAM J Comput 35:91\u2013109","journal-title":"SIAM J Comput"},{"key":"898_CR7","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1016\/0196-6774(84)90039-7","volume":"5","author":"D Dolev","year":"1984","unstructured":"Dolev D, Warmuth M (1984) Scheduling precedence graphs of bounded height. J Algorithms 5:48\u201359","journal-title":"J Algorithms"},{"key":"898_CR8","doi-asserted-by":"publisher","first-page":"964","DOI":"10.1137\/S0097539704447304","volume":"35","author":"U Feige","year":"2006","unstructured":"Feige U (2006) On sums of independent random variables with unbounded variance and estimating the average degree in a graph. SIAM J Comput 35:964\u2013984","journal-title":"SIAM J Comput"},{"key":"898_CR9","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/s10878-007-9092-2","volume":"15","author":"B Fu","year":"2006","unstructured":"Fu B, Chen Z (2006) Sublinear time width-bounded separators and their application to the protein side-chain packing problem. J Comb Optim 15:387\u2013407","journal-title":"J Comb Optim"},{"key":"898_CR10","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"O Goldreich","year":"1998","unstructured":"Goldreich O, Goldwasser S, Ron D (1998) Property testing and its connection to learning and approximation. J ACM 45:653\u2013750","journal-title":"J ACM"},{"key":"898_CR11","doi-asserted-by":"crossref","unstructured":"Goldreich O, Ron D (2006) Approximating Average Parameters of Graphs. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp. 363\u2013374","DOI":"10.1007\/11830924_34"},{"key":"898_CR12","unstructured":"Goldreich O, Ron D (2000) On testing expansion in bounded-degree graphs. In: Electronic colloquium on computational complexity, vol 7"},{"key":"898_CR13","doi-asserted-by":"publisher","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"R Graham","year":"1966","unstructured":"Graham R (1966) Bounds for certain multiprocessing anomalies. Bell Syst Tech J 45:1563\u20131581","journal-title":"Bell Syst Tech J"},{"key":"898_CR14","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"R Graham","year":"1969","unstructured":"Graham R (1969) Bounds on multiprocessing timing anomalies. SIAM J Appl Math 17:416\u2013429","journal-title":"SIAM J Appl Math"},{"key":"898_CR15","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"D Hochbaum","year":"1987","unstructured":"Hochbaum D, Shmoys D (1987) Using dual approximation algorithms for scheduling problems: theoretical and practical results. J ACM 34:144\u2013162","journal-title":"J ACM"},{"key":"898_CR16","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1287\/opre.26.1.22","volume":"26","author":"J Lenstra","year":"1978","unstructured":"Lenstra J, Kan A (1978) Complexity of scheduling under precedence constraints. Oper Res 26:22\u201335","journal-title":"Oper Res"},{"key":"898_CR17","doi-asserted-by":"publisher","first-page":"STOC16-201","DOI":"10.1137\/16M1105049","volume":"50","author":"E Levey","year":"2021","unstructured":"Levey E, Rothvoss T (2021) A (1 + $$\\epsilon $$)-approximation for makespan scheduling with precedence constraints using LP hierarchies. SIAM J Comput 50:STOC16-201-STOC16-217","journal-title":"SIAM J Comput"},{"key":"898_CR18","doi-asserted-by":"crossref","unstructured":"Ma B (2000) A polynomial time approximation scheme for the closest substring problem. In: Combinatorial pattern matching, pp 99\u2013107","DOI":"10.1007\/3-540-45123-4_10"},{"key":"898_CR19","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized algorithms","author":"R Motwani","year":"1995","unstructured":"Motwani R, Raghavan P (1995) Randomized algorithms. Cambridge University Press, Cambridge"},{"key":"898_CR20","volume-title":"Scheduling: theory, algorithms, and systems","author":"M Pinedo","year":"2008","unstructured":"Pinedo M (2008) Scheduling: theory, algorithms, and systems. Springer"},{"key":"898_CR21","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10951-017-0519-z","volume":"21","author":"D Prot","year":"2018","unstructured":"Prot D, Bellenguez-Morineau O (2018) A survey on how the structure of precedence constraints may change the complexity class of scheduling problems. J Sched 21:3\u201316","journal-title":"J Sched"},{"key":"898_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":"898_CR23","doi-asserted-by":"publisher","first-page":"1258","DOI":"10.1137\/100810502","volume":"40","author":"O Svensson","year":"2011","unstructured":"Svensson O (2011) Hardness of precedence constrained scheduling on identical machines. SIAM J Comput 40:1258\u20131274","journal-title":"SIAM J Comput"},{"key":"898_CR24","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1016\/S0022-0000(75)80008-0","volume":"10","author":"J Ullman","year":"1975","unstructured":"Ullman J (1975) NP-complete scheduling problems. J Comput Syst Sci 10:384\u2013393","journal-title":"J Comput Syst Sci"}],"container-title":["Mathematical Methods of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-025-00898-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00186-025-00898-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-025-00898-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,7]],"date-time":"2025-09-07T11:09:18Z","timestamp":1757243358000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00186-025-00898-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["898"],"URL":"https:\/\/doi.org\/10.1007\/s00186-025-00898-z","relation":{},"ISSN":["1432-2994","1432-5217"],"issn-type":[{"type":"print","value":"1432-2994"},{"type":"electronic","value":"1432-5217"}],"subject":[],"published":{"date-parts":[[2025,6]]},"assertion":[{"value":"11 September 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 April 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 May 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 July 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that thay have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Ethical approval was not required for this study as it did not involve human participants or animals.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}}]}}