{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T21:59:04Z","timestamp":1780783144583,"version":"3.54.1"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032277312","type":"print"},{"value":"9783032277329","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"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":[[2026]]},"DOI":"10.1007\/978-3-032-27732-9_37","type":"book-chapter","created":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T21:14:40Z","timestamp":1780780480000},"page":"531-545","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Minimizing Makespan in\u00a0Sublinear Time via\u00a0Weighted Random Sampling"],"prefix":"10.1007","author":[{"given":"Bin","family":"Fu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yumei","family":"Huo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hairong","family":"Zhao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,7]]},"reference":[{"key":"37_CR1","doi-asserted-by":"crossref","unstructured":"Batu, T., Berenbrink, P., Sohler, C.: A sublinear-time approximation scheme for bin packing. Theor. Comput. Sci. 410(47), 5082\u20135092 (2009). issn: 0304-3975","DOI":"10.1016\/j.tcs.2009.08.006"},{"key":"37_CR2","doi-asserted-by":"crossref","unstructured":"Behnezhad, S.: Time-optimal sublinear algorithms for matching and vertex cover. In: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 873\u2013884 (2022)","DOI":"10.1109\/FOCS52979.2021.00089"},{"key":"37_CR3","doi-asserted-by":"crossref","unstructured":"Behnezhad, S., Roghani, M., Rubinstein, A.: Sublinear time algorithms and complexity of approximate maximum matching. In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing. STOC 2023, pp. 267\u2013280. Association for Computing Machinery, Orlando (2023). isbn: 9781450399135","DOI":"10.1145\/3564246.3585231"},{"key":"37_CR4","doi-asserted-by":"crossref","unstructured":"Beretta, L., T\u011btek, J.: Better sum estimation via weighted sampling. In: Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2303\u20132338 (2022)","DOI":"10.1137\/1.9781611977073.93"},{"key":"37_CR5","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.: Sublinear geometric algorithms. SIAM J. Comput. 35, 627\u2013646 (2005)","journal-title":"SIAM J. Comput."},{"key":"37_CR6","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Sohler, C.: Estimating the weight of metric minimum spanning trees in sublinear-time. In: Proceedings of the 36th ACM Symposium on Theory of Computing, pp. 175\u2013183 (2004)","DOI":"10.1145\/1007352.1007386"},{"key":"37_CR7","doi-asserted-by":"publisher","first-page":"964","DOI":"10.1137\/S0097539704447304","volume":"35","author":"U Feige","year":"2006","unstructured":"Feige, U.: On sumes of independent random variables with unbounded variance and estimating the average degree in a graph. SIAM J. Comput. 35, 964\u2013984 (2006)","journal-title":"SIAM J. Comput."},{"key":"37_CR8","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/s10878-007-9092-2","volume":"15","author":"B Fu","year":"2008","unstructured":"Fu, B., Chen, Z.: Sublinear-time algorithms for width-bounded geometric separators and their applications to protein side-chain packing problems. J. Comb. Optim. 15, 387\u2013407 (2008)","journal-title":"J. Comb. Optim."},{"key":"37_CR9","doi-asserted-by":"crossref","unstructured":"Fu, B., Huo, Y., Zhao, H.: Sublinear algorithms for scheduling with chain precedence constraints. In: Proceedings of the 30th International Computing and Combinatorics Conference (COCOON 2024) (2024)","DOI":"10.1007\/978-981-96-1090-7_4"},{"key":"37_CR10","doi-asserted-by":"crossref","unstructured":"Fu, B., Huo, Y., Zhao, H.: Sublinear time approximation schemes for makespan minimization on parallel machines. Math. Methods Oper. Res. 101(3), 507\u2013528 (2025). issn: 1432-5217","DOI":"10.1007\/s00186-025-00898-z"},{"key":"37_CR11","unstructured":"Goldreich, O., Ron, D.: Approximating average parameters of graphs. Technical report 05-73 (2005)"},{"key":"37_CR12","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. J. ACM 45(4), 653\u2013750 (1998)","DOI":"10.1145\/285055.285060"},{"key":"37_CR13","unstructured":"Goldreich, O., Ron, D.: On testing expansion in bounded-degree graphs. Electron. Colloquium Comput. Complex. TR00 (2000)"},{"key":"37_CR14","doi-asserted-by":"crossref","unstructured":"Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45, 1563\u20131581 (1966)","DOI":"10.1002\/j.1538-7305.1966.tb01709.x"},{"key":"37_CR15","doi-asserted-by":"crossref","unstructured":"Graham, R.L.: Bounds on multiprocessing timing anomalies. J. SIAM Appl. Math. 17, 416\u2013429 (1969)","DOI":"10.1137\/0117039"},{"key":"37_CR16","doi-asserted-by":"crossref","unstructured":"Hochbaum, D.S., Landy, D.: Scheduling semiconductor burn-in operations to minimize total flowtime. Oper. Res. 45(6), 874\u2013885 (1997)","DOI":"10.1287\/opre.45.6.874"},{"issue":"1","key":"37_CR17","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"DS Hochbaum","year":"1987","unstructured":"Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems theoretical and practical results. J. ACM 34(1), 144\u2013162 (1987)","journal-title":"J. ACM"},{"key":"37_CR18","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1145\/321941.321951","volume":"23","author":"E Horowitz","year":"1976","unstructured":"Horowitz, E., Sahni, S.: Exact and approximate algorithms for scheduling nonidentical processors. J. ACM 23, 317\u2013327 (1976)","journal-title":"J. ACM"},{"key":"37_CR19","doi-asserted-by":"publisher","unstructured":"K Jansen. An EPTAS for scheduling jobs on uniform processors: using an MILP relaxation with a constant number of integral variables. SIAM J. Disc. Math. 24(2), 457\u2013485 (2010). https:\/\/doi.org\/10.1137\/090749451","DOI":"10.1137\/090749451"},{"key":"37_CR20","doi-asserted-by":"publisher","unstructured":"Jansen, K., Klein, K.M., Verschae, J.: Closing the gap for makespan scheduling via sparsification techniques. Math. Oper. Res. 45(4), 1371\u20131392 (2020). https:\/\/doi.org\/10.1287\/MOOR.2019.1036","DOI":"10.1287\/MOOR.2019.1036"},{"issue":"3","key":"37_CR21","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0020-0190(89)90223-8","volume":"31","author":"JY-T Leung","year":"1989","unstructured":"Leung, J.Y.-T.: Bin packing with restricted piece sizes. Inf. Process. Lett. 31(3), 145\u2013149 (1989). https:\/\/doi.org\/10.1016\/0020-0190(89)90223-8","journal-title":"Inf. Process. Lett."},{"key":"37_CR22","doi-asserted-by":"crossref","unstructured":"Motwani, R., Panigrahy, R., Xu, Y.: Estimating sum by weighted sampling. In: International Colloquium on Automata, Languages and Programming, (ICALP), July 2007, pp. 53\u201364 (2007)","DOI":"10.1007\/978-3-540-73420-8_7"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-27732-9_37","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T21:14:42Z","timestamp":1780780482000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-27732-9_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032277312","9783032277329"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-27732-9_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"7 June 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IWOCA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Combinatorial Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Clermont-Ferrand","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 June 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 June 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"37","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwoca2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/iwoca2026.limos.fr\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}