Scheduling With Time Discounts
For researchers in online scheduling and algorithmic game theory, this work extends the classic weighted packet scheduling problem to a more realistic time-discounted setting, revealing limitations of existing methods and providing new optimal algorithms.
This paper introduces a financial version of online packet scheduling where packet values decay over time, and presents a memoryless deterministic algorithm achieving optimal competitive ratio for discount factors up to ≈0.77, along with a randomized algorithm that outperforms any deterministic algorithm for all discount rates.
We study a \emph{financial} version of the online problem of scheduling weighted packets with deadlines. The main novelty is that, while prior works assume packets have \emph{fixed} weights, we consider packets with \emph{time-decaying} values. Such considerations are natural in financial environments, where the present value of future actions may be discounted. We analyze the competitive ratios of scheduling algorithms under a range of discount rates encompassing the traditional undiscounted case where weights are fixed (i.e., a discount rate of 1), the fully discounted myopic case (i.e., a rate of 0), and those in between. We show how existing methods from the literature perform suboptimally in the more general discounted setting. Notably, we devise a novel memoryless deterministic algorithm, and prove that for discount factors up to $\approx 0.77$, it guarantees the best competitive ratio attainable by deterministic algorithms. Moreover, we develop a randomized algorithm and prove that it outperforms the best possible deterministic algorithm for any discount rate.