{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,23]],"date-time":"2026-09-23T05:44:01Z","timestamp":1790142241720,"version":"4.0.1"},"publisher-location":"Singapore","reference-count":34,"publisher":"Springer Nature Singapore","isbn-type":[{"value":"9789819548385","type":"print"},{"value":"9789819548392","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-981-95-4839-2_1","type":"book-chapter","created":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T01:35:47Z","timestamp":1767317747000},"page":"3-14","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Complexity and\u00a0Approximation Algorithms for\u00a0Fixed Charge Transportation Problems"],"prefix":"10.1007","author":[{"given":"Yong","family":"Chen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shi","family":"Li","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zihao","family":"Liang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,1,2]]},"reference":[{"key":"1_CR1","unstructured":"Hirsch, W.M., Dantzig, G.B.: Notes on linear programming: part XIX\u2014the fixed charge problem. RAND Research Memorandum 1383, RAND Corporation, Santa Monica, CA (1954)"},{"issue":"3","key":"1_CR2","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1002\/nav.3800150306","volume":"15","author":"WM Hirsch","year":"1968","unstructured":"Hirsch, W.M., Dantzig, G.B.: The fixed charge problem. Naval Res. Logist. Q. 15(3), 413\u2013424 (1968)","journal-title":"Naval Res. Logist. Q."},{"issue":"1","key":"1_CR3","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0377-2217(93)90263-M","volume":"71","author":"RL Rardin","year":"1993","unstructured":"Rardin, R.L., Wolsey, L.A.: Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problems. Eur. J. Oper. Res. 71(1), 95\u2013109 (1993)","journal-title":"Eur. J. Oper. Res."},{"issue":"3","key":"1_CR4","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1002\/net.10068","volume":"41","author":"F Ortega","year":"2003","unstructured":"Ortega, F., Wolsey, L.A.: A branch-and-cut algorithm for the single commodity, uncapacitated, fixed-charge network flow problem. Networks 41(3), 143\u2013158 (2003)","journal-title":"Networks"},{"issue":"3","key":"1_CR5","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1002\/net.20098","volume":"47","author":"Y Agarwal","year":"2006","unstructured":"Agarwal, Y.: K-partition-based facets of the network design problem. Networks 47(3), 123\u2013139 (2006)","journal-title":"Networks"},{"issue":"6","key":"1_CR6","doi-asserted-by":"publisher","first-page":"1229","DOI":"10.1016\/j.dam.2008.04.022","volume":"157","author":"A Frangioni","year":"2009","unstructured":"Frangioni, A., Gendron, B.: Reformulations of the multicommodity capacitated network design problem. Discret. Appl. Math. 157(6), 1229\u20131241 (2009)","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"1_CR7","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1002\/net.20395","volume":"57","author":"C Raack","year":"2011","unstructured":"Raack, C., Koster, A.M.C.A., Orlowski, S., Wessaly, R.: On cut-based inequalities for capacitated network design polyhedra. Networks 57(2), 141\u2013156 (2011)","journal-title":"Networks"},{"issue":"4","key":"1_CR8","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1002\/nav.3800260408","volume":"26","author":"J Fisk","year":"1979","unstructured":"Fisk, J., McKeown, P.G.: The pure fixed charge transportation problem. Naval Res. Logist. Q. 26(4), 631\u2013641 (1979)","journal-title":"Naval Res. Logist. Q."},{"issue":"3","key":"1_CR9","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/0166-218X(92)00177-N","volume":"48","author":"M G\u00f6the-Lundgren","year":"1994","unstructured":"G\u00f6the-Lundgren, M., Larsson, T.: A set covering reformulation of the pure fixed charge transportation problem. Discret. Appl. Math. 48(3), 245\u2013259 (1994)","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"1_CR10","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1287\/opre.16.2.268","volume":"16","author":"KG Murty","year":"1968","unstructured":"Murty, K.G.: Solving the fixed charge problem by ranking the extreme points. Oper. Res. 16(2), 268\u2013279 (1968)","journal-title":"Oper. Res."},{"issue":"6","key":"1_CR11","doi-asserted-by":"publisher","first-page":"1529","DOI":"10.1287\/opre.19.6.1529","volume":"19","author":"P Gray","year":"1971","unstructured":"Gray, P.: Exact solution of the fixed-charge transportation problem. Oper. Res. 19(6), 1529\u20131538 (1971)","journal-title":"Oper. Res."},{"issue":"3","key":"1_CR12","doi-asserted-by":"publisher","first-page":"638","DOI":"10.1287\/opre.1120.1041","volume":"60","author":"Y Agarwal","year":"2012","unstructured":"Agarwal, Y., Aneja, Y.: Fixed-charge transportation problem: Facets of the projection polyhedron. Oper. Res. 60(3), 638\u2013654 (2012)","journal-title":"Oper. Res."},{"issue":"3","key":"1_CR13","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1007\/s10898-018-0661-y","volume":"72","author":"Y Zhao","year":"2018","unstructured":"Zhao, Y., Larsson, T., R\u00f6nnberg, E., Pardalos, P.M.: The fixed charge transportation problem: a strong formulation based on Lagrangian decomposition and column generation. J. Global Optim. 72(3), 517\u2013538 (2018). https:\/\/doi.org\/10.1007\/s10898-018-0661-y","journal-title":"J. Global Optim."},{"issue":"2","key":"1_CR14","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1287\/trsc.2017.0742","volume":"52","author":"A Mingozzi","year":"2018","unstructured":"Mingozzi, A., Roberti, R.: An exact algorithm for the fixed charge transportation problem based on matching source and sink patterns. Transp. Sci. 52(2), 229\u2013496 (2018)","journal-title":"Transp. Sci."},{"issue":"10","key":"1_CR15","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1287\/mnsc.22.10.1116","volume":"22","author":"J Kennigton","year":"1976","unstructured":"Kennigton, J., Unger, E.: A new branch-and-bound algorithm for the fixed-charge transportation problem. Manage. Sci. 22(10), 1116\u20131126 (1976)","journal-title":"Manage. Sci."},{"issue":"3","key":"1_CR16","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1287\/opre.29.3.448","volume":"29","author":"RS Barr","year":"1981","unstructured":"Barr, R.S., Glover, F., Klingman, D.: A new optimization method for large scale fixed charge transportation problems. Oper. Res. 29(3), 448\u2013463 (1981)","journal-title":"Oper. Res."},{"issue":"1","key":"1_CR17","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1002\/nav.3800310115","volume":"31","author":"AV Cabot","year":"1984","unstructured":"Cabot, A.V., Erenguc, S.S.: Some branch and bound procedures for fixed cost transportation problems. Naval Res. Logist. Q. 31(1), 145\u2013154 (1984)","journal-title":"Naval Res. Logist. Q."},{"issue":"6","key":"1_CR18","first-page":"1197","volume":"61","author":"R Roberti","year":"2015","unstructured":"Roberti, R., Bartolini, E., Mingozzi, A.: The fixed charge transportation problem: an exact algorithm based on a new integer programming formulation. Manage. Sci. 61(6), 1197\u20131471 (2015)","journal-title":"Manage. Sci."},{"issue":"3","key":"1_CR19","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0377-2217(89)90441-4","volume":"42","author":"DD Wright","year":"1989","unstructured":"Wright, D.D., von Lanzenauer, C.H.: Solving the fixed charge problem with Lagrangian relaxation and cost allocation heuristics. Eur. J. Oper. Res. 42(3), 305\u2013312 (1989)","journal-title":"Eur. J. Oper. Res."},{"issue":"2\u20133","key":"1_CR20","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1016\/S0377-2217(97)00284-1","volume":"106","author":"M Sun","year":"1998","unstructured":"Sun, M., Aronson, J.E., McKeown, P.G., Drinka, D.: A tabu search heuristic procedure for the fixed charge transportation problem. Eur. J. Oper. Res. 106(2\u20133), 441\u2013456 (1998)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"1_CR21","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/s10479-008-0483-2","volume":"172","author":"JS Aguado","year":"2009","unstructured":"Aguado, J.S.: Fixed charge transportation problems: A new heuristic approach based on Lagrangean relaxation and the solving of core problems. Ann. Oper. Res. 172(1), 45\u201369 (2009)","journal-title":"Ann. Oper. Res."},{"issue":"5","key":"1_CR22","doi-asserted-by":"publisher","first-page":"973","DOI":"10.1287\/opre.2014.1288","volume":"62","author":"E Buson","year":"2014","unstructured":"Buson, E., Roberti, R., Toth, P.: A reduced-cost iterated local search heuristic for the fixed-charge transportation problem. Oper. Res. 62(5), 973\u20131201 (2014)","journal-title":"Oper. Res."},{"issue":"1","key":"1_CR23","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/BF02283688","volume":"25","author":"G Guisewite","year":"1990","unstructured":"Guisewite, G., Pardalos, P.: Minimum concave-cost network flow problems: applications, complexity, and algorithms. Ann. Oper. Res. 25(1), 75\u201399 (1990)","journal-title":"Ann. Oper. Res."},{"issue":"8","key":"1_CR24","doi-asserted-by":"publisher","first-page":"879","DOI":"10.1080\/00207390500137837","volume":"36","author":"K Kowalski","year":"2005","unstructured":"Kowalski, K.: On the structure of the fixed charge transportation problem. Int. J. Math. Educ. Sci. Technol. 36(8), 879\u2013888 (2005)","journal-title":"Int. J. Math. Educ. Sci. Technol."},{"key":"1_CR25","doi-asserted-by":"publisher","first-page":"2306","DOI":"10.1016\/j.mcm.2011.05.039","volume":"54","author":"S Schrenk","year":"2011","unstructured":"Schrenk, S., Finke, G., Cung, V.D.: Two classical transportation problems revisited: pure constant fixed charges and the paradox. Math. Comput. Model. 54, 2306\u20132315 (2011)","journal-title":"Math. Comput. Model."},{"key":"1_CR26","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0020-0190(91)90246-E","volume":"37","author":"K Kann","year":"1991","unstructured":"Kann, K.: Maximum bounded 3-dimensional matching is MAX SNP-complete. Inf. Process. Lett. 37, 27\u201335 (1991)","journal-title":"Inf. Process. Lett."},{"key":"1_CR27","unstructured":"Berman, P., Karpinski, M.: Improved approximation lower bounds on small occurrence optimization. Electron. Colloq. Comput. Complexity (ECCC) 10(008) (2003)"},{"key":"1_CR28","doi-asserted-by":"crossref","unstructured":"Cygan, M.: Improved approximation for 3-dimensional matching via bounded pathwidth local search. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 509\u2013518 (2013)","DOI":"10.1109\/FOCS.2013.61"},{"key":"1_CR29","doi-asserted-by":"crossref","unstructured":"Furer, M., Yu, H.: Approximating the k-set packing problem by local improvements. In: International Symposium on Combinatorial Optimization (ISCO), pp. 408\u2013420 (2014)","DOI":"10.1007\/978-3-319-09174-7_35"},{"issue":"2","key":"1_CR30","first-page":"298","volume":"52","author":"F Grandoni","year":"2022","unstructured":"Grandoni, F., Laekhanukit, B., Li, S.: $$O(log^{2}k\/loglog k)$$-approximation algorithm for directed Steiner tree: a tight quasi-polynomial time algorithm. SIAM J. Comput. 52(2), 298\u2013322 (2022)","journal-title":"SIAM J. Comput."},{"key":"1_CR31","doi-asserted-by":"crossref","unstructured":"Halperin, E., Krauthgamer, R.: Polylogarithmic inapproximability. In: ACM Symposium on Theory of Computing (STOC), pp. 585\u2013594 (2003)","DOI":"10.1145\/780542.780628"},{"issue":"2","key":"1_CR32","doi-asserted-by":"publisher","first-page":"1612","DOI":"10.1287\/moor.2021.1181","volume":"47","author":"R Ghuge","year":"2022","unstructured":"Ghuge, R., Nagarajan, V.: Quasi-polynomial algorithms for submodular tree orienteering and directed network design problems. Math. Oper. Res. 47(2), 1612\u20131630 (2022)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"1_CR33","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1006\/jagm.1999.1042","volume":"33","author":"M Charikar","year":"1999","unstructured":"Charikar, M., Chekuri, C., Cheung, T., Dai, Z., Goel, A., Guha, S., Li, M.: Approximation algorithms for directed steiner problems. J. Algorithms 33(1), 73\u201391 (1999)","journal-title":"J. Algorithms"},{"issue":"1","key":"1_CR34","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF02523690","volume":"18","author":"A Zelikovsky","year":"1997","unstructured":"Zelikovsky, A.: A series of approximation algorithms for the acyclic directed steiner tree problem. Algorithmica 18(1), 99\u2013110 (1997)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-95-4839-2_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T01:35:49Z","timestamp":1767317749000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-95-4839-2_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9789819548385","9789819548392"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-981-95-4839-2_1","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":"2 January 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TAMC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual Conference on Theory and Applications of Models of Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Jinan","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":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 September 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 September 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tamc2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.maths.sdnu.edu.cn\/TAMC2025.htm","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}