Metraipolis › archive › dc_2de444dcb4bb

Minimization Prophet Inequality with Bounded Costs — arXiv:2609.06464

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.06464
License (as archived): CC0-1.0
Archived: 2026-10-16T15:31:47.247Z
SHA-256 of the archived text: 1b498b168936412abab083d2d6a10d0b61a19a75683dbe2d036770fe873f6c25
Stable URL of this page: https://metraipolis.com/documento/dc_2de444dcb4bb

How to cite

Minimization Prophet Inequality with Bounded Costs — arXiv:2609.06464 — arXiv (en), https://arxiv.org/abs/2609.06464 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2de444dcb4bb (Metraipolis archive dc_2de444dcb4bb, sha256 1b498b168936412abab083d2d6a10d0b61a19a75683dbe2d036770fe873f6c25)

BibTeX

@misc{dc2de444dcb4bb,
  title = {Minimization Prophet Inequality with Bounded Costs — arXiv:2609.06464},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.06464},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2de444dcb4bb; sha256 1b498b168936412abab083d2d6a10d0b61a19a75683dbe2d036770fe873f6c25},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.06464. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study the cost-minimization prophet inequality problem, in which a decision-maker sequentially observes $n$ independent and identically distributed (IID) random variables. After each observation, the decision-maker must either accept the current realization and stop, or reject it and continue with the next variable. The goal is to minimize the selected value. Unlike the classical maximization setting, if none of the first $n-1$ values is accepted, the final realization must be selected. Esfandiari et al. (SIDMA 2017) showed that this problem does not admit constant-competitive online algorithms in general, which motivates subsequent work on restricted distribution classes, such as entire distributions (Livanos and Mehta, SODA 2024) and distributions with bounded extreme values (Livanos and Mehta, EC 2025). In this work, we focus on distributions with bounded support. For distributions supported on $[1,b]$, we characterize the competitive ratio of online algorithms as a function of both $b$ and $n$. We consider both distribution-aware and distribution-oblivious settings. In the distribution-aware case, we provide a nearly tight characterization of the optimal online algorithm, showing that its competitive ratio is at most $b^{(1-1/n)^n}$ for all $n\geq 2$. More significantly, we design a distribution-oblivious algorithm that achieves the same guarantee, with a sequence of predetermined thresholds that depend only on $b$ and $n$. Furthermore, we extend our analysis to the non-IID setting, where we show that a simple single-threshold algorithm attains an asymptotically optimal competitive ratio of $\Theta(\sqrt{b})$.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-09 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.06464 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T15:15:08.333Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).