{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T19:04:58Z","timestamp":1757617498835,"version":"3.44.0"},"publisher-location":"Singapore","reference-count":20,"publisher":"Springer Nature Singapore","isbn-type":[{"type":"print","value":"9789819610891"},{"type":"electronic","value":"9789819610907"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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":[[2025]]},"DOI":"10.1007\/978-981-96-1090-7_4","type":"book-chapter","created":{"date-parts":[[2025,3,4]],"date-time":"2025-03-04T16:33:17Z","timestamp":1741105997000},"page":"42-53","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Sublinear Algorithms for\u00a0Scheduling with\u00a0Chain Precedence Constraints"],"prefix":"10.1007","author":[{"given":"Bin","family":"Fu","sequence":"first","affiliation":[]},{"given":"Yumei","family":"Huo","sequence":"additional","affiliation":[]},{"given":"Hairong","family":"Zhao","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,3,5]]},"reference":[{"key":"4_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\u201349), 5082\u20135092 (2009)","DOI":"10.1016\/j.tcs.2009.08.006"},{"key":"4_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/978-3-642-29700-7_16","volume-title":"Frontiers in Algorithmics and Algorithmic Aspects in Information and Management","author":"R Beigel","year":"2012","unstructured":"Beigel, R., Fu, B.: A dense hierarchy of sublinear time approximation schemes for bin packing. In: Snoeyink, J., Lu, P., Su, K., Wang, L. (eds.) AAIM\/FAW -2012. LNCS, vol. 7285, pp. 172\u2013181. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-29700-7_16"},{"key":"4_CR3","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/PL00020913","volume":"49","author":"P Brucker","year":"1999","unstructured":"Brucker, P., Hurink, J., Kubiak, W.: Scheduling identical jobs with chain precedence constraints on two uniform machines. Math. Methods OR 49, 211\u2013219 (1999)","journal-title":"Math. Methods OR"},{"issue":"3","key":"4_CR4","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(3), 627\u2013646 (2005)","journal-title":"SIAM J. Comput."},{"key":"4_CR5","doi-asserted-by":"publisher","first-page":"916","DOI":"10.1007\/s00224-020-10011-y","volume":"65","author":"G Cormode","year":"2021","unstructured":"Cormode, G., Vesel\u00fd, P.: Streaming algorithms for bin packing and vector scheduling. Theory Comput. Syst 65, 916\u2013942 (2021)","journal-title":"Theory Comput. Syst"},{"key":"4_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-642-16367-8_5","volume-title":"Property Testing","author":"A Czumaj","year":"2010","unstructured":"Czumaj, A., Sohler, C.: Sublinear-time algorithms. In: Goldreich, O. (ed.) Property Testing. LNCS, vol. 6390, pp. 41\u201364. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-16367-8_5"},{"issue":"2","key":"4_CR7","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0890-5401(91)90009-Q","volume":"92","author":"J Du","year":"1991","unstructured":"Du, J., Leung, J.Y.-T., Young, G.H.: Scheduling chain-structured tasks to minimize makespan and mean flow time. Inf. Comput. 92(2), 219\u2013236 (1991)","journal-title":"Inf. Comput."},{"issue":"4","key":"4_CR8","doi-asserted-by":"publisher","first-page":"964","DOI":"10.1137\/S0097539704447304","volume":"35","author":"U Feige","year":"2006","unstructured":"Feige, U.: On sums of independent random variables with unbounded variance and estimating the average degree in a graph. SIAM J. Comput. 35(4), 964\u2013984 (2006)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"4_CR9","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1016\/0022-0000(85)90041-8","volume":"31","author":"P Flajolet","year":"1985","unstructured":"Flajolet, P., Martin, G.N.: Probabilistic counting algorithms for data base applications. J. Comput. Syst. Sci. 31(2), 182\u2013209 (1985)","journal-title":"J. Comput. Syst. Sci."},{"key":"4_CR10","first-page":"387","volume":"15","author":"F Bin","year":"2006","unstructured":"Bin, F., Chen, Z.: Sublinear time width-bounded separators and their application to the protein side-chain packing problem. J. Comb. Optim. 15, 387\u2013407 (2006)","journal-title":"J. Comb. Optim."},{"key":"4_CR11","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1016\/j.dam.2022.06.019","volume":"320","author":"F Bin","year":"2022","unstructured":"Bin, F., Huo, Y., Zhao, H.: Streaming algorithms for multitasking scheduling with shared processing. Discrete Appl. Math. 320, 346\u2013355 (2022)","journal-title":"Discrete Appl. Math."},{"key":"4_CR12","doi-asserted-by":"publisher","first-page":"113937","DOI":"10.1016\/j.tcs.2023.113937","volume":"961","author":"F Bin","year":"2023","unstructured":"Bin, F., Huo, Y., Zhao, H.: Streaming approximation scheme for minimizing total completion time on parallel machines subject to varying processing capacity. Theor. Comput. Sci. 961, 113937 (2023)","journal-title":"Theor. Comput. Sci."},{"key":"4_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/11830924_34","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"O Goldreich","year":"2006","unstructured":"Goldreich, O., Ron, D.: Approximating average parameters of graphs. In: D\u00edaz, J., Jansen, K., Rolim, J.D.P., Zwick, U. (eds.) APPROX\/RANDOM -2006. LNCS, vol. 4110, pp. 363\u2013374. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11830924_34"},{"key":"4_CR14","doi-asserted-by":"publisher","first-page":"841","DOI":"10.1287\/opre.9.6.841","volume":"9","author":"TC Hu","year":"1961","unstructured":"Hu, T.C.: Parallel sequencing and assembly line problems. Oper. Res. 9, 841\u2013848 (1961)","journal-title":"Oper. Res."},{"key":"4_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/3-540-45123-4_10","volume-title":"Combinatorial Pattern Matching","author":"B Ma","year":"2000","unstructured":"Ma, B.: A polynomial time approximation scheme for the closest substring problem. In: Giancarlo, R., Sankoff, D. (eds.) CPM 2000. LNCS, vol. 1848, pp. 99\u2013107. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-45123-4_10"},{"issue":"1","key":"4_CR16","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1145\/2627692.2627694","volume":"43","author":"A McGregor","year":"2014","unstructured":"McGregor, A.: Graph stream algorithms: a survey. SIGMOD Rec. 43(1), 9\u201320 (2014)","journal-title":"SIGMOD Rec."},{"issue":"1","key":"4_CR17","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. Manage. Sci. 6(1), 1\u201312 (1959)","journal-title":"Manage. Sci."},{"issue":"3","key":"4_CR18","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/0304-3975(80)90061-4","volume":"12","author":"JI Munro","year":"1980","unstructured":"Munro, J.I., Paterson, M.S.: Selection and sorting with limited storage. Theoret. Comput. Sci. 12(3), 315\u2013323 (1980)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"4_CR19","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1561\/0400000002","volume":"1","author":"S Muthukrishnan","year":"2005","unstructured":"Muthukrishnan, S.: Data streams: algorithms and applications. Found. Trends Theor. Comput. Sci. 1(2), 117\u2013236 (2005)","journal-title":"Found. Trends Theor. Comput. Sci."},{"issue":"4","key":"4_CR20","doi-asserted-by":"publisher","first-page":"1562","DOI":"10.1137\/100791075","volume":"25","author":"R Rubinfeld","year":"2011","unstructured":"Rubinfeld, R., Shapira, A.: Sublinear time algorithms. SIAM J. Discret. Math. 25(4), 1562\u20131588 (2011)","journal-title":"SIAM J. Discret. Math."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-96-1090-7_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T06:56:45Z","timestamp":1757141805000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-96-1090-7_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9789819610891","9789819610907"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-981-96-1090-7_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"5 March 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Shanghai","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 August 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 August 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/anl.sjtu.edu.cn\/cocoon2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}