Complexity and approximation algorithms for fixed charge transportation problems

The Fixed Charge Transportation (FCT) problem models shipping a commodity from n sources to m sinks, where the cost consists of a linear component and a fixed component. Despite extensive research on exact and heuristic algorithms for FCT, its approximability and computational complexity remain poorly understood. In this work, we initiate a systematic study of the complexity and approximability of FCT and its variants. We distinguish between cases with and without linear costs—defining the Pure FCT (PFCT) problem when linear costs are omitted—and classify whether fixed costs are general, sink-independent (-S), or uniform (-U), yielding six core variants. We provide a complete characterization of the existence of O(1)-approximation algorithms for these variants. Specifically, we design 2-approximation algorithms for FCT-U and PFCT-S, and a (6/5+ϵ)-approximation for PFCT-U. On the negative side, we prove that FCT and PFCT are NP-hard to approximate within a factor of O(log^2−ϵ⁡(max⁡{n,m})) for any constant ϵ>0, FCT-S is NP-hard to approximate within clog⁡(max⁡{n,m}), and PFCT-U is APX-hard. Additionally, we develop an Efficient Parameterized Approximation Scheme (EPAS) for PFCT parameterized by the number of sources n, and an O(1/ϵ)-bicriteria approximation for FCT that allows a 1±ϵ factor violation of sink demands. Finally, we consider the unbalanced setting where supply exceeds demand, providing 2, 2+ϵ, and 7/5-approximation algorithms for the unbalanced versions of FCT-U, PFCT-S, and PFCT-U, respectively.