{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T09:55:32Z","timestamp":1742982932532,"version":"3.40.3"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030931759"},{"type":"electronic","value":"9783030931766"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-93176-6_3","type":"book-chapter","created":{"date-parts":[[2021,12,16]],"date-time":"2021-12-16T22:09:57Z","timestamp":1639692597000},"page":"27-37","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Approximation Algorithms for\u00a0the\u00a0Maximum Bounded Connected Bipartition Problem"],"prefix":"10.1007","author":[{"given":"Yajie","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weidong","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaofei","family":"Liu","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":[[2021,12,17]]},"reference":[{"key":"3_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.: Max-min partitioning of grid graphs into connected components. Networks 32, 115\u2013125 (1998)","journal-title":"Networks"},{"key":"3_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.: A polynomial-time algorithm for max-min partitioning of ladders. Theory Comput. Syst. 34, 353\u2013374 (2001)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"3_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.: Shifting algorithms for tree partitioning with general weighting functions. J. Algorithms 4(2), 101\u2013120 (1983)","journal-title":"J. Algorithms"},{"key":"3_CR4","first-page":"177","volume":"9","author":"F Chataigner","year":"2007","unstructured":"Chataigner, F., Salgado, L., Wakabayashi, Y.: Approximation and inapproximability results on balanced connected partitions of graphs. Discrete Math. Theor. Comput. Sci. 9, 177\u2013192 (2007)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"3_CR5","doi-asserted-by":"publisher","unstructured":"Chen, G., Chen, Y., Chen, Z.-Z., Lin, G., Liu, T., Zhang, A.: Approximation algorithms for the maximally balanced connected graph tripartition problem. J. Comb. Optim., 1\u201321 (2020). https:\/\/doi.org\/10.1007\/s10878-020-00544-w","DOI":"10.1007\/s10878-020-00544-w"},{"key":"3_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.: Fully polynomial time approximation scheme to maximize early work on parallel machines with common due date. Eur. J. Oper. Res. 284, 67\u201374 (2020)","journal-title":"Eur. J. Oper. Res."},{"key":"3_CR7","doi-asserted-by":"crossref","unstructured":"Chen, X., Wang, W., Xie, P., Zhang, X., Sterna, M., Blazewicz, J.: Exact and heuristic algorithms for scheduling on two identical machines with early work maximization. Comput. Ind. Eng. 144, Article No. 106449 (2020)","DOI":"10.1016\/j.cie.2020.106449"},{"key":"3_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1007\/978-3-030-36412-0_11","volume-title":"Combinatorial Optimization and Applications","author":"Y Chen","year":"2019","unstructured":"Chen, Y., Chen, Z.-Z., Lin, G., Xu, Y., Zhang, A.: Approximation algorithms for maximally balanced connected graph partition. In: Li, Y., Cardei, M., Huang, Y. (eds.) COCOA 2019. LNCS, vol. 11949, pp. 130\u2013141. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-36412-0_11"},{"key":"3_CR9","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.: Approximating the maximally balanced connected partition problem in graphs. Inf. Process. Lett. 60, 225\u2013230 (1996)","journal-title":"Inf. Process. Lett."},{"key":"3_CR10","doi-asserted-by":"crossref","unstructured":"Choi, B., Park, M., Kim, K., Min, Y.: A parallel machine scheduling problem maximizing total weighted early work. Asia-Pac. J. Oper. Res. Article No. 2150007 (2021)","DOI":"10.1142\/S021759592150007X"},{"key":"3_CR11","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/0166-218X(85)90008-3","volume":"10","author":"M Dyer","year":"1985","unstructured":"Dyer, M., Frieze, A.: On the complexity of partitioning graphs into connected subgraphs. Discret. Appl. Math. 10, 139\u2013153 (1985)","journal-title":"Discret. Appl. Math."},{"key":"3_CR12","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.: Computing an ST-numbering. Theoret. Comput. Sci. 2, 339\u2013344 (1976)","journal-title":"Theoret. Comput. Sci."},{"key":"3_CR13","unstructured":"Frederickson, G.: Optimal algorithms for tree partitioning. In: Symposium on Discrete Algorithms, pp. 168\u2013177 (1991)"},{"key":"3_CR14","unstructured":"Frederickson, G., Samson, Z.: Optimal parametric search for path and tree partitioning. arXiv:abs\/1711.00599 (2017)"},{"issue":"9","key":"3_CR15","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, R.L.: Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45(9), 1563\u20131581 (1966)","journal-title":"Bell Syst. Tech. J."},{"issue":"4","key":"3_CR16","doi-asserted-by":"publisher","first-page":"1229","DOI":"10.1007\/s11590-020-01632-w","volume":"15","author":"L Guan","year":"2020","unstructured":"Guan, L., Li, W., Xiao, M.: Online algorithms for the mixed ring loading problem with two nodes. Optim. Lett. 15(4), 1229\u20131239 (2020). https:\/\/doi.org\/10.1007\/s11590-020-01632-w","journal-title":"Optim. Lett."},{"issue":"1","key":"3_CR17","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.: A common approximation framework for early work, late work, and resource leveling problems. Eur. J. Oper. Res. 286(1), 129\u2013137 (2020)","journal-title":"Eur. J. Oper. Res."},{"key":"3_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/978-3-030-67899-9_38","volume-title":"Algorithms and Discrete Applied Mathematics","author":"S Jana","year":"2021","unstructured":"Jana, S., Pandit, S., Roy, S.: Balanced connected graph partition. In: Mudgal, A., Subramanian, C.R. (eds.) CALDAM 2021. LNCS, vol. 12601, pp. 487\u2013499. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-67899-9_38"},{"key":"3_CR19","unstructured":"Lempel, A., Even, S., Cederbaum, I.: An algorithm for planarity testing of graphs. In: Rosenstiehl, P. (ed.) International Symposium 1966, Theory of Graphs, pp. 215\u2013232. Gordon and Breach, New York; Dunod, Paris (1966)"},{"key":"3_CR20","unstructured":"Li, W.: Improved approximation schemes for early work scheduling on identical parallel machines with common due date. arXiv:abs\/2007.12388 (2020)"},{"key":"3_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1007\/3-540-51815-0_37","volume-title":"Recent Issues in Pattern Analysis and Recognition","author":"M Lucertini","year":"1989","unstructured":"Lucertini, M., Perl, Y., Simeone, B.: Image enhancement by path partitioning. In: Cantoni, V., Creutzburg, R., Levialdi, S., Wolf, G. (eds.) PAR 1988. LNCS, vol. 399, pp. 12\u201322. Springer, Heidelberg (1989). https:\/\/doi.org\/10.1007\/3-540-51815-0_37"},{"issue":"2\u20133","key":"3_CR22","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.: Most uniform path partitioning and its use in image processing. Discret. Appl. Math. 42(2\u20133), 227\u2013256 (1993)","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"3_CR23","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/S0167-9473(96)00062-X","volume":"24","author":"M Maravalle","year":"1997","unstructured":"Maravalle, M., Simeone, B., Naldini, R.: Clustering on trees. Comput. Stat. Data Anal. 24(2), 217\u2013234 (1997)","journal-title":"Comput. Stat. Data Anal."},{"key":"3_CR24","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1016\/j.ejor.2020.12.059","volume":"293","author":"F Miyazawa","year":"2021","unstructured":"Miyazawa, F., Moura, P., Ota, M., Wakabayashi, Y.: Partitioning a graph into balanced connected classes: formulations, separation and experiments. Eur. J. Oper. Res. 293, 826\u2013836 (2021)","journal-title":"Eur. J. Oper. Res."},{"key":"3_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3381419","volume":"16","author":"S Soltan","year":"2020","unstructured":"Soltan, S., Yannakakis, M., Zussman, G.: Doubly balanced connected graph partitioning. ACM Trans. Algorithms 16, 1\u201324 (2020)","journal-title":"ACM Trans. Algorithms"},{"key":"3_CR26","doi-asserted-by":"crossref","unstructured":"Sterna, M.: Late and early work scheduling: a survey. Omega-Int. J. Manag. Sci. 104(10), Artical No. 102453 (2021)","DOI":"10.1016\/j.omega.2021.102453"},{"issue":"3","key":"3_CR27","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.: Polynomial time approximation scheme for two parallel machines scheduling with a common due date to maximize early work. J. Optim. Theory Appl. 174(3), 927\u2013944 (2017)","journal-title":"J. Optim. Theory Appl."},{"key":"3_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1007\/978-3-642-24983-9_19","volume-title":"Computational Geometry, Graphs and Applications","author":"BY Wu","year":"2011","unstructured":"Wu, B.Y.: A 7\/6-approximation algorithm for the max-min connected bipartition problem on grid graphs. In: Akiyama, J., Bo, J., Kano, M., Tan, X. (eds.) CGGA 2010. LNCS, vol. 7033, pp. 188\u2013194. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-24983-9_19"},{"key":"3_CR29","doi-asserted-by":"crossref","unstructured":"Wu, B.: Fully polynomial time approximation schemes for the max-min connected partition problem on interval graphs. Discret Math. Algorithm Appl. 4, Artical No. 1250005 (2012)","DOI":"10.1142\/S179383091250005X"},{"key":"3_CR30","doi-asserted-by":"publisher","first-page":"592","DOI":"10.1007\/s10878-012-9481-z","volume":"26","author":"B Wu","year":"2013","unstructured":"Wu, B.: Algorithms for the minimum non-separating path and the balanced connected bipartition problems on grid graphs. J. Comb. Optim. 26, 592\u2013607 (2013)","journal-title":"J. Comb. Optim."}],"container-title":["Lecture Notes in Computer Science","Algorithmic Aspects in Information and Management"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-93176-6_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T05:44:09Z","timestamp":1641015849000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-93176-6_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030931759","9783030931766"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-93176-6_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"17 December 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"AAIM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithmic Applications in Management","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 December 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 December 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"aaim2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/theory.utdallas.edu\/AAIM2021\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"OCS","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"62","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"38","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"61% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}