# Online Allocation Problem with Two-sided Resource Constraints

arXiv: https://arxiv.org/abs/2112.13964 · HTML: https://mlsanity.com/paper/2112.13964/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 24 references that are in the map.
- First posted on arXiv 28 Dec 2021.

## Builds on (most cited first, 7 of 7)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2002.10421/) (2020)
- [Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds](https://mlsanity.com/paper/1909.05499/) (2019)
- [Simple and Fast Algorithm for Binary Integer and Online Linear Programming](https://mlsanity.com/paper/2003.02513/) (2020)
- [Regularized Online Allocation Problems: Fairness and Beyond](https://mlsanity.com/paper/2007.00514/) (2020)
- [Primal Beats Dual on Online Packing LPs in the Random-Order Model](https://mlsanity.com/paper/1311.2578/) (2013)
- [Joint Online Learning and Decision-making via Dual Mirror Descent](https://mlsanity.com/paper/2104.09750/) (2021)

## Abstract (arXiv)

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(fracvarepsilonxi^*-varepsilon)big) or big(1-O(fracvarepsilonxi^*-√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.