On the complexity of a special basis problem in LP (Q1315997)

For a linear program in standard form, the paper shows that the problem of finding a cheapest feasible basic vector among those containing a specified variable as a basic variable is NP-hard. Here, the cost of a feasible vector is defined to be the cost of the associated basic feasible solution. The idea of the proof is to formulate the following NP-hard problem as a special case of the investigated one through a balanced transportation model: Let \(d_ 1,\dots,d_ n\in \mathbb{N}\) with \(\sum^ n_{j=1} d_ j= w\), \(w\) even. Find a subset \(S\subseteq \{1,\dots,n\}\) satisfying \(-2+ {w\over 2}\leq \sum_{j\in S} d_ j\leq 2+{w\over 2}\).