  In this paper, we investigate the online allocation problem of maximizing the
overall revenue subject to both lower and upper bound constraints. Compared to
the extensively studied online problems with only resource upper bounds, the
two-sided constraints affect the prospects of resource consumption more
severely. As a result, only limited violations of constraints or pessimistic
competitive bounds could be guaranteed. To tackle the challenge, we define a
measure of feasibility $\xi^*$ to evaluate the hardness of this problem, and
estimate this measurement by an optimization routine with theoretical
guarantees. We propose an online algorithm adopting a constructive framework,
where we initialize a threshold price vector using the estimation, then
dynamically update the price vector and use it for decision-making at each
step. It can be shown that the proposed algorithm is
$\big(1-O(\frac{\varepsilon}{\xi^*-\varepsilon})\big)$ or
$\big(1-O(\frac{\varepsilon}{\xi^*-\sqrt{\varepsilon}})\big)$ competitive with
high probability for $\xi^*$ known or unknown respectively. To the best of our
knowledge, this is the first result establishing a nearly optimal competitive
algorithm for solving two-sided constrained online allocation problems with a
high probability of feasibility.
