Online Allocation Problem with Two-sided Resource Constraints
It addresses a challenging variant of online allocation for resource management, offering the first nearly optimal competitive algorithm with high feasibility probability, which is incremental as it builds on prior work with only upper bounds.
The paper tackles the online allocation problem with both lower and upper resource constraints, proposing an algorithm that achieves nearly optimal competitive ratios with high probability, specifically (1-O(ε/(ξ*-ε))) or (1-O(ε/(ξ*-√ε))) depending on whether the feasibility measure ξ* is known or unknown.
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 $ξ^*$ 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}{ξ^*-\varepsilon})\big)$ or $\big(1-O(\frac{\varepsilon}{ξ^*-\sqrt{\varepsilon}})\big)$ competitive with high probability for $ξ^*$ 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.