{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,2]],"date-time":"2026-09-02T13:22:18Z","timestamp":1788355338858,"version":"build-2803163510"},"reference-count":39,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,12,1]],"date-time":"2026-12-01T00:00:00Z","timestamp":1796083200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,12,1]],"date-time":"2026-12-01T00:00:00Z","timestamp":1796083200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,12,1]],"date-time":"2026-12-01T00:00:00Z","timestamp":1796083200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2026,12,1]],"date-time":"2026-12-01T00:00:00Z","timestamp":1796083200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2026,12,1]],"date-time":"2026-12-01T00:00:00Z","timestamp":1796083200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2026,12,1]],"date-time":"2026-12-01T00:00:00Z","timestamp":1796083200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2026,12,1]],"date-time":"2026-12-01T00:00:00Z","timestamp":1796083200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12471301"],"award-info":[{"award-number":["12471301"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12371316"],"award-info":[{"award-number":["12371316"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100011246","name":"State Key Laboratory of Novel Software Technology","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100011246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[2026,12]]},"DOI":"10.1016\/j.jcss.2026.103830","type":"journal-article","created":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T00:54:57Z","timestamp":1781312097000},"page":"103830","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["Complexity and approximation algorithms for fixed charge transportation problems"],"prefix":"10.1016","volume":"162","author":[{"given":"Zihao","family":"Liang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shi","family":"Li","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yong","family":"Chen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhou","family":"Xu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/j.jcss.2026.103830_br0010","article-title":"Notes on Linear Programming: Part XIX\u2014The Fixed Charge Problem","volume":"vol. 1383","author":"Hirsch","year":"1954"},{"issue":"3","key":"10.1016\/j.jcss.2026.103830_br0020","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1002\/nav.3800150306","article-title":"The fixed charge problem","volume":"15","author":"Hirsch","year":"1968","journal-title":"Nav. Res. Logist. Q."},{"issue":"1","key":"10.1016\/j.jcss.2026.103830_br0030","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0377-2217(93)90263-M","article-title":"Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problems","volume":"71","author":"Rardin","year":"1993","journal-title":"Eur. J. Oper. Res."},{"issue":"3","key":"10.1016\/j.jcss.2026.103830_br0040","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1002\/net.10068","article-title":"A branch-and-cut algorithm for the single commodity, uncapacitated, fixed-charge network flow problem","volume":"41","author":"Ortega","year":"2003","journal-title":"Networks"},{"issue":"3","key":"10.1016\/j.jcss.2026.103830_br0050","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1002\/net.20098","article-title":"K-partition-based facets of the network design problem","volume":"47","author":"Agarwal","year":"2006","journal-title":"Networks"},{"issue":"6","key":"10.1016\/j.jcss.2026.103830_br0060","doi-asserted-by":"crossref","first-page":"1229","DOI":"10.1016\/j.dam.2008.04.022","article-title":"Reformulations of the multicommodity capacitated network design problem","volume":"157","author":"Frangioni","year":"2009","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"10.1016\/j.jcss.2026.103830_br0070","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1002\/net.20395","article-title":"On cut-based inequalities for capacitated network design polyhedra","volume":"57","author":"Raack","year":"2011","journal-title":"Networks"},{"issue":"4","key":"10.1016\/j.jcss.2026.103830_br0080","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1002\/nav.3800260408","article-title":"The pure fixed charge transportation problem","volume":"26","author":"Fisk","year":"1979","journal-title":"Nav. Res. Logist. Q."},{"issue":"3","key":"10.1016\/j.jcss.2026.103830_br0090","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/0166-218X(92)00177-N","article-title":"A set covering reformulation of the pure fixed charge transportation problem","volume":"48","author":"G\u00f6the-Lundgren","year":"1994","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"10.1016\/j.jcss.2026.103830_br0100","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1287\/opre.16.2.268","article-title":"Solving the fixed charge problem by ranking the extreme points","volume":"16","author":"Murty","year":"1968","journal-title":"Oper. Res."},{"issue":"6","key":"10.1016\/j.jcss.2026.103830_br0110","doi-asserted-by":"crossref","first-page":"1529","DOI":"10.1287\/opre.19.6.1529","article-title":"Exact solution of the fixed-charge transportation problem","volume":"19","author":"Gray","year":"1971","journal-title":"Oper. Res."},{"issue":"3","key":"10.1016\/j.jcss.2026.103830_br0120","doi-asserted-by":"crossref","first-page":"638","DOI":"10.1287\/opre.1120.1041","article-title":"Fixed-charge transportation problem: facets of the projection polyhedron","volume":"60","author":"Agarwal","year":"2012","journal-title":"Oper. Res."},{"key":"10.1016\/j.jcss.2026.103830_br0130","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1007\/s10898-018-0661-y","article-title":"The fixed charge transportation problem: a strong formulation based on Lagrangian decomposition and column generation","volume":"72","author":"Zhao","year":"2018","journal-title":"J. Glob. Optim."},{"issue":"2","key":"10.1016\/j.jcss.2026.103830_br0140","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1287\/trsc.2017.0742","article-title":"An exact algorithm for the fixed charge transportation problem based on matching source and sink patterns","volume":"52","author":"Mingozzi","year":"2018","journal-title":"Transp. Sci."},{"issue":"10","key":"10.1016\/j.jcss.2026.103830_br0150","doi-asserted-by":"crossref","first-page":"1116","DOI":"10.1287\/mnsc.22.10.1116","article-title":"A new branch-and-bound algorithm for the fixed-charge transportation problem","volume":"22","author":"Kennigton","year":"1976","journal-title":"Manag. Sci."},{"issue":"3","key":"10.1016\/j.jcss.2026.103830_br0160","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1287\/opre.29.3.448","article-title":"A new optimization method for large scale fixed charge transportation problems","volume":"29","author":"Barr","year":"1981","journal-title":"Oper. Res."},{"issue":"1","key":"10.1016\/j.jcss.2026.103830_br0170","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1002\/nav.3800310115","article-title":"Some branch and bound procedures for fixed cost transportation problems","volume":"31","author":"Cabot","year":"1984","journal-title":"Nav. Res. Logist. Q."},{"issue":"6","key":"10.1016\/j.jcss.2026.103830_br0180","doi-asserted-by":"crossref","first-page":"1275","DOI":"10.1287\/mnsc.2014.1947","article-title":"The fixed charge transportation problem: an exact algorithm based on a new integer programming formulation","volume":"61","author":"Roberti","year":"2015","journal-title":"Manag. Sci."},{"issue":"3","key":"10.1016\/j.jcss.2026.103830_br0190","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0377-2217(89)90441-4","article-title":"Solving the fixed charge problem with Lagrangian relaxation and cost allocation heuristics","volume":"42","author":"Wright","year":"1989","journal-title":"Eur. J. Oper. Res."},{"issue":"2\u20133","key":"10.1016\/j.jcss.2026.103830_br0200","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1016\/S0377-2217(97)00284-1","article-title":"A tabu search heuristic procedure for the fixed charge transportation problem","volume":"106","author":"Sun","year":"1998","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"10.1016\/j.jcss.2026.103830_br0210","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/s10479-008-0483-2","article-title":"Fixed charge transportation problems: a new heuristic approach based on Lagrangean relaxation and the solving of core problems","volume":"172","author":"Aguado","year":"2009","journal-title":"Ann. Oper. Res."},{"issue":"5","key":"10.1016\/j.jcss.2026.103830_br0220","doi-asserted-by":"crossref","first-page":"1095","DOI":"10.1287\/opre.2014.1288","article-title":"A reduced-cost iterated local search heuristic for the fixed-charge transportation problem","volume":"62","author":"Buson","year":"2014","journal-title":"Oper. Res."},{"issue":"1","key":"10.1016\/j.jcss.2026.103830_br0230","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/BF02283688","article-title":"Minimum concave-cost network flow problems: applications, complexity, and algorithms","volume":"25","author":"Guisewite","year":"1990","journal-title":"Ann. Oper. Res."},{"issue":"8","key":"10.1016\/j.jcss.2026.103830_br0240","doi-asserted-by":"crossref","first-page":"879","DOI":"10.1080\/00207390500137837","article-title":"On the structure of the fixed charge transportation problem","volume":"36","author":"Kowalski","year":"2005","journal-title":"Int. J. Math. Educ. Sci. Technol."},{"key":"10.1016\/j.jcss.2026.103830_br0250","doi-asserted-by":"crossref","first-page":"2306","DOI":"10.1016\/j.mcm.2011.05.039","article-title":"Two classical transportation problems revisited: pure constant fixed charges and the paradox","volume":"54","author":"Schrenk","year":"2011","journal-title":"Math. Comput. Model."},{"key":"10.1016\/j.jcss.2026.103830_br0260","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0020-0190(91)90246-E","article-title":"Maximum bounded 3-dimensional matching is MAX SNP-complete","volume":"37","author":"Kann","year":"1991","journal-title":"Inf. Process. Lett."},{"issue":"008","key":"10.1016\/j.jcss.2026.103830_br0270","article-title":"Improved approximation lower bounds on small occurrence optimization","volume":"10","author":"Berman","year":"2003","journal-title":"Electron. Colloq. Comput. Complex."},{"key":"10.1016\/j.jcss.2026.103830_br0280","series-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA)","first-page":"509","article-title":"Improved approximation for 3-dimensional matching via bounded pathwidth local search","author":"Cygan","year":"2013"},{"key":"10.1016\/j.jcss.2026.103830_br0290","series-title":"International Symposium on Combinatorial Optimization (ISCO)","first-page":"408","article-title":"Approximating the k-set packing problem by local improvements","author":"Furer","year":"2014"},{"issue":"3","key":"10.1016\/j.jcss.2026.103830_br0300","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","article-title":"Approximation algorithms for combinatorial problems","volume":"9","author":"Johnson","year":"1974","journal-title":"J. Comput. Syst. Sci."},{"key":"10.1016\/j.jcss.2026.103830_br0310","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","article-title":"On the ratio of optimal integral and fractional covers","author":"Lov\u00e1sz","year":"1975","journal-title":"Discrete Math."},{"issue":"5","key":"10.1016\/j.jcss.2026.103830_br0320","doi-asserted-by":"crossref","first-page":"960","DOI":"10.1145\/185675.306789","article-title":"On the hardness of approximating minimization problems","volume":"41","author":"Lund","year":"1994","journal-title":"J. ACM"},{"issue":"4","key":"10.1016\/j.jcss.2026.103830_br0330","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","article-title":"A threshold of ln n for approximating set cover","volume":"45","author":"Feige","year":"1998","journal-title":"J. ACM"},{"key":"10.1016\/j.jcss.2026.103830_br0340","series-title":"ACM Symposium on Theory of Computing (STOC)","first-page":"624","article-title":"Analytical approach to parallel repetition","author":"Dinur","year":"2014"},{"issue":"2","key":"10.1016\/j.jcss.2026.103830_br0350","first-page":"298","article-title":"O(log2k\/loglogk)-approximation algorithm for directed Steiner tree: a tight quasi-polynomial time algorithm","volume":"52","author":"Grandoni","year":"2022","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.jcss.2026.103830_br0360","series-title":"ACM Symposium on Theory of Computing (STOC)","first-page":"585","article-title":"Polylogarithmic inapproximability","author":"Halperin","year":"2003"},{"issue":"2","key":"10.1016\/j.jcss.2026.103830_br0370","doi-asserted-by":"crossref","first-page":"1612","DOI":"10.1287\/moor.2021.1181","article-title":"Quasi-polynomial algorithms for submodular tree orienteering and directed network design problems","volume":"47","author":"Ghuge","year":"2022","journal-title":"Math. Oper. Res."},{"issue":"1","key":"10.1016\/j.jcss.2026.103830_br0380","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1006\/jagm.1999.1042","article-title":"Approximation algorithms for directed Steiner problems","volume":"33","author":"Charikar","year":"1999","journal-title":"J. Algorithms"},{"issue":"1","key":"10.1016\/j.jcss.2026.103830_br0390","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF02523690","article-title":"A series of approximation algorithms for the acyclic directed Steiner tree problem","volume":"18","author":"Zelikovsky","year":"1997","journal-title":"Algorithmica"}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000026000760?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000026000760?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,9,2]],"date-time":"2026-09-02T13:08:27Z","timestamp":1788354507000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0022000026000760"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,12]]},"references-count":39,"alternative-id":["S0022000026000760"],"URL":"https:\/\/doi.org\/10.1016\/j.jcss.2026.103830","relation":{},"ISSN":["0022-0000"],"issn-type":[{"value":"0022-0000","type":"print"}],"subject":[],"published":{"date-parts":[[2026,12]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Complexity and approximation algorithms for fixed charge transportation problems","name":"articletitle","label":"Article Title"},{"value":"Journal of Computer and System Sciences","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.jcss.2026.103830","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.","name":"copyright","label":"Copyright"}],"article-number":"103830"}}