2341. Online Resource Allocation Problem with Departures
Invited abstract in session MC-38: Automating the Design, Generation and Control of Optimization Algorithms 2, stream Data Science meets Optimization.
Monday, 12:30-14:00Room: Michael Sadler LG19
Authors (first author is the speaker)
| 1. | Yusuf Amidu
|
| Mathematics, Khalifa University |
Abstract
In this paper we propose a novel primal-dual algorithm for the following online resource allocation problem. Requests arrive over time to a set of resources and upon arrival, the time a request may occupy a resource becomes known. We assume that the duration of stay of a request is deterministic, may depend on the resource and that resources may have different capacities. The goal is to decide whether to accept/reject a request upon arrival and to which resource to allocate it such that the reward obtained over a time T is maximized. We show that the proposed primal-dual algorithm achieves a competitive ratio of O(R/r), where R is the maximum reward and r is the minimum reward that can be obtained. Through numerical experiments, we show that the primal-dual algorithm has lower computation times than a recent algorithm proposed in the literature, while having a similar performance in practical instances.
Keywords
- Algorithms
- Simulation
- Optimization Modeling
Status: accepted
Back to the list of papers