| | |
| | |
Stat |
Members: 3645 Articles: 2'504'928 Articles rated: 2609
25 April 2024 |
|
| | | |
|
Article overview
| |
|
A Unified Model for the Two-stage Offline-then-Online Resource Allocation | Yifan Xu
; Pan Xu
; Jianping Pan
; Jun Tao
; | Date: |
12 Dec 2020 | Abstract: | With the popularity of the Internet, traditional offline resource allocation
has evolved into a new form, called online resource allocation. It features the
online arrivals of agents in the system and the real-time decision-making
requirement upon the arrival of each online agent. Both offline and online
resource allocation have wide applications in various real-world matching
markets ranging from ridesharing to crowdsourcing. There are some emerging
applications such as rebalancing in bike sharing and trip-vehicle dispatching
in ridesharing, which involve a two-stage resource allocation process. The
process consists of an offline phase and another sequential online phase, and
both phases compete for the same set of resources. In this paper, we propose a
unified model which incorporates both offline and online resource allocation
into a single framework. Our model assumes non-uniform and known arrival
distributions for online agents in the second online phase, which can be
learned from historical data. We propose a parameterized linear programming
(LP)-based algorithm, which is shown to be at most a constant factor of $1/4$
from the optimal. Experimental results on the real dataset show that our
LP-based approaches outperform the LP-agnostic heuristics in terms of
robustness and effectiveness. | Source: | arXiv, 2012.06845 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |