{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:19:23Z","timestamp":1740122363886,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12071417"],"award-info":[{"award-number":["12071417"]}],"id":[{"id":"10.13039\/501100001809","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":[[2023,1]]},"DOI":"10.1007\/s10878-022-00981-9","type":"journal-article","created":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T09:03:47Z","timestamp":1673255027000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Combinatorial approximation algorithms for the maximum bounded connected bipartition problem"],"prefix":"10.1007","volume":"45","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1650-2625","authenticated-orcid":false,"given":"Xiaofei","family":"Liu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yajie","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weidong","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jinhua","family":"Yang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,1,9]]},"reference":[{"key":"981_CR1","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1002\/(SICI)1097-0037(199809)32:2<115::AID-NET4>3.0.CO;2-E","volume":"32","author":"R Becker","year":"1998","unstructured":"Becker R, Lari I, Lucertini M, Simeone B (1998) Max-min partitioning of grid graphs into connected components. Networks 32:115\u2013125","journal-title":"Networks"},{"key":"981_CR2","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/s00224-001-0008-8","volume":"34","author":"R Becker","year":"2001","unstructured":"Becker R, Lari I, Lucertini M, Simeone B (2001) A polynomial-time algorithm for max-min partitioning of ladders. Theory Comput Syst 34:353\u2013374","journal-title":"Theory Comput Syst"},{"key":"981_CR3","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/0196-6774(83)90039-1","volume":"4","author":"R Becker","year":"1983","unstructured":"Becker R, Perl Y (1983) Shifting algorithms for tree partitioning with general weighting functions. J Algorithms 4:101\u2013120","journal-title":"J Algorithms"},{"key":"981_CR4","first-page":"177","volume":"9","author":"F Chataigner","year":"2007","unstructured":"Chataigner F, Salgado L, Wakabayashi Y (2007) Approximation and inapproximability results on balanced connected partitions of graphs. Discrete Math Theor Comput Sci 9:177\u2013192","journal-title":"Discrete Math Theor Comput Sci"},{"key":"981_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-020-00544-w","author":"G Chen","year":"2020","unstructured":"Chen G, Chen Y, Chen Z, Lin G, Liu T, Zhang A (2020) Approximation algorithms for the maximally balanced connected graph tripartition problem. J Comb Optim. https:\/\/doi.org\/10.1007\/s10878-020-00544-w","journal-title":"J Comb Optim"},{"key":"981_CR6","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.ejor.2019.12.003","volume":"284","author":"X Chen","year":"2020","unstructured":"Chen X, Liang Y, Sterna M, Wang W, Blazewicz J (2020) Fully polynomial time approximation scheme to maximize early work on parallel machines with common due date. Eur J Oper Res 284:67\u201374","journal-title":"Eur J Oper Res"},{"key":"981_CR7","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1007\/978303036412011","volume-title":"Combinatorial optimization and applications 2019, Lecture notes in computer science","author":"Y Chen","year":"2019","unstructured":"Chen Y, Chen Z, Lin G, Xu Y, Zhang A (2019) Approximation algorithms for maximally balanced connected graph partition. In: Li Y, Cardei M, Huang Y (eds) Combinatorial optimization and applications 2019, Lecture notes in computer science, vol 11949. Springer, Cham, pp 130\u2013141. https:\/\/doi.org\/10.1007\/978303036412011"},{"key":"981_CR8","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/S0020-0190(96)00175-5","volume":"60","author":"J Chleb\u00edkov\u00e1","year":"1996","unstructured":"Chleb\u00edkov\u00e1 J (1996) Approximating the maximally balanced connected partition problem in graphs. Inf Process Lett 60:225\u2013230","journal-title":"Inf Process Lett"},{"key":"981_CR9","doi-asserted-by":"crossref","unstructured":"Choi B, Park M, Kim K, Min, Y (2021) A parallel machine scheduling problem maximizing total weighted early work. Asia-Pacific J Oper Res 38(6), Article No. 2150007","DOI":"10.1142\/S021759592150007X"},{"key":"981_CR10","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1016\/0304-3975(76)90086-4","volume":"2","author":"S Even","year":"1976","unstructured":"Even S, Tarjan R (1976) Computing an st-numbering. Theor Comput Sci 2:339\u2013344","journal-title":"Theor Comput Sci"},{"key":"981_CR11","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W.H Freeman and Company, USA"},{"issue":"9","key":"981_CR12","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 RL (1966) Bounds for certain multiprocessing anomalies. Bell Syst Tech J 45(9):1563\u20131581","journal-title":"Bell Syst Tech J"},{"key":"981_CR13","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/j.ejor.2020.03.032","volume":"286","author":"P Gy\u00f6rgyi","year":"2020","unstructured":"Gy\u00f6rgyi P, Kis T (2020) A common approximation framework for early work, late work, and resource leveling problems. Eur J Oper Res 286:129\u2013137","journal-title":"Eur J Oper Res"},{"key":"981_CR14","first-page":"215","volume-title":"International Symposium 1966, Theory of Graphs","author":"A Lempel","year":"1966","unstructured":"Lempel A, Even S, Cederbaum I (1966) An algorithm for planarity testing of graphs. In: Rosenstiehl P (ed) International Symposium 1966, Theory of Graphs. Gordon and Breach, New York, Dunod, Paris, pp 215\u2013232"},{"key":"981_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/s40305-022-00402-y","author":"W Li","year":"2022","unstructured":"Li W (2022) Improved approximation schemes for early work scheduling on identical parallel machines with common due date. J Oper Res Soc China. https:\/\/doi.org\/10.1007\/s40305-022-00402-y","journal-title":"J Oper Res Soc China"},{"key":"981_CR16","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/978-3-030-93176-6_3","volume-title":"Algorithmic aspects in information and management. AAIM 2021. Lecture notes in computer science","author":"Y Li","year":"2021","unstructured":"Li Y, Li W, Liu X, Yang J (2021) Approximation algorithms for the maximum bounded connected Bipartition problem. In: Wu W, Du H (eds) Algorithmic aspects in information and management. AAIM 2021. Lecture notes in computer science, vol 13153. Springer, Cham, pp 27\u201337. https:\/\/doi.org\/10.1007\/978-3-030-93176-6_3"},{"key":"981_CR17","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/0166-218X(93)90048-S","volume":"42","author":"M Lucertini","year":"1993","unstructured":"Lucertini M, Perl Y, Simeone B (1993) Most uniform path partitioning and its use in image processing. Discrete Appl Math 42:227\u2013256","journal-title":"Discrete Appl Math"},{"key":"981_CR18","doi-asserted-by":"publisher","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","volume":"36","author":"RC Prim","year":"1957","unstructured":"Prim RC (1957) Shortest connection networks and some generalizations. Bell Syst Tech J 36:1389\u20131401","journal-title":"Bell Syst Tech J"},{"key":"981_CR19","doi-asserted-by":"crossref","unstructured":"Soltan S, Yannakakis M, Zussman G (2020) Doubly balanced connected graph partitioning. ACM Trans Algorithms 16, Article No. 20","DOI":"10.1145\/3381419"},{"key":"981_CR20","doi-asserted-by":"crossref","unstructured":"Sterna M (2021) Late and early work scheduling: a survey. Omega-Int J Manag Sci 104, Artical No. 102453","DOI":"10.1016\/j.omega.2021.102453"},{"key":"981_CR21","doi-asserted-by":"publisher","first-page":"927","DOI":"10.1007\/s10957-017-1147-7","volume":"174","author":"M Sterna","year":"2017","unstructured":"Sterna M, Czerniachowska K (2017) Polynomial time approximation scheme for two parallel machines scheduling with a common due date to maximize early work. J Optim Theory Appl 174:927\u2013944","journal-title":"J Optim Theory Appl"},{"key":"981_CR22","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1007\/978364224983919","volume-title":"Computational geometry, graphs and applications 2010. Lecture notes in computer science","author":"B Wu","year":"2010","unstructured":"Wu B (2010) A $$\\frac{7}{6}$$-approximation algorithm for the max-min connected bipartition problem on grid graphs. In: Akiyama J, Bo J, Kano M, Tan X (eds) Computational geometry, graphs and applications 2010. Lecture notes in computer science, vol 7033. Springer, Berlin, Heidelberg, pp 188\u2013194. https:\/\/doi.org\/10.1007\/978364224983919"},{"key":"981_CR23","doi-asserted-by":"crossref","unstructured":"Wu B (2012) Fully polynomial time approximation schemes for the max-min connected partition problem on interval graphs. Discret Math Algorithm Appl 4, Artical No. 1250005","DOI":"10.1142\/S179383091250005X"},{"key":"981_CR24","doi-asserted-by":"publisher","first-page":"592","DOI":"10.1007\/s10878-012-9481-z","volume":"26","author":"B Wu","year":"2013","unstructured":"Wu B (2013) Algorithms for the minimum non-separating path and the balanced connected bipartition problems on grid graphs. J Comb Optim 26:592\u2013607","journal-title":"J Comb Optim"},{"key":"981_CR25","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1016\/0377-2217(94)00335-1","volume":"91","author":"T Yamada","year":"1996","unstructured":"Yamada T, Takahashi H, Kataoka S (1996) A heuristic algorithm for the mini-max spanning forest problem. Eur J Oper Res 91:565\u2013572","journal-title":"Eur J Oper Res"},{"key":"981_CR26","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/978-3-030-93176-6_13","volume-title":"Algorithmic aspects in information and management. AAIM 2021. Lecture notes in computer science","author":"M Xiao","year":"2021","unstructured":"Xiao M, Liu X, Li W (2021) Semi-online early work maximization problem on two hierarchical machines with partial information of processing time. In: Wu W, Du H (eds) Algorithmic aspects in information and management. AAIM 2021. Lecture notes in computer science, vol 13153. Springer, Cham, pp 146\u2013156. https:\/\/doi.org\/10.1007\/978-3-030-93176-6_13"},{"key":"981_CR27","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1007\/978-3-031-16081-3_5","volume-title":"Algorithmic aspects in information and management. AAIM 2022. Lecture notes in computer science","author":"M Xiao","year":"2022","unstructured":"Xiao M, Bai X, Li W (2022) Online early work maximization problem on two hierarchical machines with buffer or rearrangements. In: Ni Q, Wu W (eds) Algorithmic aspects in information and management. AAIM 2022. Lecture notes in computer science, vol 13513. Springer, Cham, pp 46\u201354. https:\/\/doi.org\/10.1007\/978-3-031-16081-3_5"},{"key":"981_CR28","doi-asserted-by":"publisher","unstructured":"Xiao M, Liu X, Li W, Chen X, Sterna M, Blazewicz J (2022b) Online and semi-online scheduling on two hierarchical machines with a common due date to maximize the total early work. arXiv:2209.08704. https:\/\/doi.org\/10.48550\/arXiv.2209.08704","DOI":"10.48550\/arXiv.2209.08704"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00981-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-022-00981-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00981-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,4]],"date-time":"2023-02-04T07:51:48Z","timestamp":1675497108000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-022-00981-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["981"],"URL":"https:\/\/doi.org\/10.1007\/s10878-022-00981-9","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2023,1]]},"assertion":[{"value":"30 December 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 January 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"51"}}