  We present several new complexity results for the entropic regularized
algorithms that approximately solve the optimal transport (OT) problem between
two discrete probability measures with at most $n$ atoms. First, we improve the
complexity bound of a greedy variant of Sinkhorn, known as \textit{Greenkhorn},
from $\widetilde{O}(n^2\varepsilon^{-3})$ to
$\widetilde{O}(n^2\varepsilon^{-2})$. Notably, our result can match the best
known complexity bound of Sinkhorn and help clarify why Greenkhorn
significantly outperforms Sinkhorn in practice in terms of row/column updates
as observed by~\citet{Altschuler-2017-Near}. Second, we propose a new
algorithm, which we refer to as \textit{APDAMD} and which generalizes an
adaptive primal-dual accelerated gradient descent (APDAGD)
algorithm~\citep{Dvurechensky-2018-Computational} with a prespecified mirror
mapping $\phi$. We prove that APDAMD achieves the complexity bound of
$\widetilde{O}(n^2\sqrt{\delta}\varepsilon^{-1})$ in which $\delta>0$ stands
for the regularity of $\phi$. In addition, we show by a counterexample that the
complexity bound of $\widetilde{O}(\min\{n^{9/4}\varepsilon^{-1},
n^2\varepsilon^{-2}\})$ proved for APDAGD before is invalid and give a refined
complexity bound of $\widetilde{O}(n^{5/2}\varepsilon^{-1})$. Further, we
develop a \textit{deterministic} accelerated variant of Sinkhorn via appeal to
estimated sequence and prove the complexity bound of
$\widetilde{O}(n^{7/3}\varepsilon^{-4/3})$. As such, we see that accelerated
variant of Sinkhorn outperforms Sinkhorn and Greenkhorn in terms of
$1/\varepsilon$ and APDAGD and accelerated alternating minimization
(AAM)~\citep{Guminov-2021-Combination} in terms of $n$. Finally, we conduct the
experiments on synthetic and real data and the numerical results show the
efficiency of Greenkhorn, APDAMD and accelerated Sinkhorn in practice.
