of [@km11; @km13].

(Kitahara and Mizuno) Let $\x^*$ be partitioned using $(B^k,N^k)$ and $z^*$ be the optimal value of (\[LP\]), we have $$\c^{\Tr} \x^k - z^* 
\le \gamma_D^k \| \x_{N^k}^* \|_1.
\label{1stEst}$$ \[firstL\]

Since $\x^*$ is partitioned using $(B^k,N^k)$, we have $(\x_{B^k}^* , \x_{N^k}^*) \ge \0$, and $$\begin{aligned}
\A_{B^k}\x_{B^k}^* +\A_{N^k}\x_{N^k}^*= \b. \nonumber\end{aligned}$$ This gives $$\begin{aligned}
\x_{B^k}^*  
= \A_{B^k}^{-1} \b -\A_{B^k}^{-1} \A_{N^k}\x_{N^k}^*.
\nonumber \end{aligned}$$ Therefore, we have $$\begin{aligned}
\c^{\Tr} \x^* & = & 
\c_{B^k}^{\Tr}\x_{B^k}^* + {\c}_{N^k}^{\Tr}\x_{N^k}^*  
\nonumber \\
& = & \c_{B^k}^{\Tr}  \A_{B^k}^{-1} \b 
-{\c}_{B^k}^{\Tr}\A_{B^k}^{-1}\A_{N^k}\x_{N^k}^*
+{\c}_{N^k}^{\Tr}\x_{N^k}^*   
\nonumber \\
 & = & \c_{B^k}^{\Tr}  \A_{B^k}^{-1} \b 
+ ({\c}_{N^k}^{\Tr}-{\c}_{B^k}^{\Tr}\A_{B^k}^{-1}\A_{N^k})
\x_{N^k}^*.\end{aligned}$$ Using this relation and (\[cNbar\]), we have $$\begin{aligned}
z^* & = & \c^{\Tr} \x^*   \nonumber \\
& = & \c_{B^k}^{\Tr}  \A_{B^k}^{-1} \b 
+ \bar{\c}_{N^k}^{\Tr}\x_{N^k}^*  \nonumber \\ 
& \ge &  \c^{\Tr} \x^k -  \gamma_D^k \| \x_{N^k}^* \|_1.
\label{est1}\end{aligned}$$ This finishes the proof. [&lt;1.5em -1.5em plus0em minus0.5em height0.75em width0.5em depth0.25em]{}

If $B^* \ne B^k$, i.e., $\x^k$ is not an optimizer, from (\[est1\]), it must have $\bar{\c}_{N^k}^{\Tr}\x_{N^k}^* <0$. Therefore, there are $j^k \in N^k$ such that $$\bar{c}_{j^k} <0 \hspace{0.1in} \mbox{and}
\hspace{0.1in} x_{j^k}^*>0.
\label{NkBstar}$$ This means that for $j^k \in N^k \cap B^*$, $x_{j^k}$ should be the entering variable. The problem is that one does not know $B^*$ 