Scheduling With Time Discounts

Yotam Gafni and Aviv Yaish

Papers from arXiv.org

Abstract: 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.

Date: 2024-02, Revised 2026-06
New Economics Papers: this item is included in nep-pay
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://arxiv.org/pdf/2402.08549 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2402.08549

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().