English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

The Fixed Charge Transportation (FCT) problem models transportation scenarioswhere we need to send a commodity from $n$ sources to $m$ sinks, and the costof sending a commodity from a source to a sink consists of a linear componentand a fixed component. Despite extensive research on exponential time exactalgorithms and heuristic algorithms for FCT and its variants, theirapproximability and computational complexity are not well understood.  In this work, we initiate a systematic study of the approximability andcomplexity of these problems. When there are no linear costs, we call theproblem the Pure Fixed Charge Transportation (PFCT) problem. We alsodistinguish between cases with general, sink-independent, and uniform fixedcosts; we use the suffixes ``-S'' and ``-U'' to denote the latter two cases,respectively. This gives us six variants of the FCT problem.  We give a complete characterization of the existence of $O(1)$-approximationalgorithms for these variants. In particular, we give $2$-approximationalgorithms for FCT-U and PFCT-S, and a $(6/5 + \epsilon)$-approximation forPFCT-U. On the negative side, we prove that FCT and PFCT are NP-hard toapproximate within a factor of $O(\log^{2-\epsilon} (\max\{n, m\}))$ for anyconstant $\epsilon > 0$, FCT-S is NP-hard to approximate within a factor of$c\log (\max\{n, m\})$ for some constant $c> 0$, and PFCT-U is APX-hard.Additionally, we design an Efficient Parameterized Approximation Scheme (EPAS)for PFCT when parameterized by the number $n$ of sources, and an$O(1/\epsilon)$-bicriteria approximation for the FCT problem, when we areallowed to violate the demand constraints for sinks by a factor of $1\pm\epsilon$.

Complexity and Approximation Algorithms for Fixed Charge Transportation Problems