A $1/2$-Approximation for Pandora's Problem with Deadlines

概要

Pandora's problem is a fundamental model of sequential search in which opening each box incurs a cost. We study the variant with deadlines, where each box has a publicly known deadline for both opening and selection. We prove that a simple threshold strategy achieves a $1/2$-approximation to the optimal expected utility, improving the previous guarantee arbitrarily close to $1/4$ due to Amanatidis et al. (2025).

参考リンク

• Paper ↗

リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。

実装を始めるプロンプト

参考リンクを確認したうえで、次の内容をコピーして利用できます。

# 論文・記事
A $1/2$-Approximation for Pandora's Problem with Deadlines

# 概要
Pandora's problem is a fundamental model of sequential search in which opening each box incurs a cost. We study the variant with deadlines, where each box has a publicly known deadline for both…

# 原典
https://arxiv.org/abs/2610.13775

上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。