The Transportation Problem with Exclusionary Side Constraints

We consider the so-called Transportation Problem with Exclusionary Side Constraints (TPESC), which is a generalization of the ordinary transportation problem. We determine the complexity status for each of two special cases of this problem, by proving NP-completeness, and by exhibiting a pseudo-polynomial time algorithm. For the general problem, we show that it cannot be approximated with a constant performance ratio in polynomial time (unless P=NP). These results settle the complexity status of the TPESC