Pairwise-independent contention resolution

• 成果类型: Article; Early Access
• 署名作者: Gupta, Anupam; Hu, Jinqiao; Kehne, Gregory; Levin, Roie
• 署名单位: New York University; University of Warwick; Washington University (WUSTL); Rutgers University System; Rutgers University New Brunswick
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-025-02253-w
• 发表日期: 2025
• 关键词: prophet inequalities; matroid secretary

摘要

We study online contention resolution schemes (OCRSes) and prophet inequalities for non-product distributions. Specifically, when the active set is sampled according to a pairwise-independent (PI) distribution, we show a (1-ok(1))\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(1-o_k(1))$$\end{document}-selectable OCRS for uniform matroids of rank k, and Omega(1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Omega (1)$$\end{document}-selectable OCRSes for laminar, graphic, cographic, transversal, and regular matroids. These imply prophet inequalities with the same ratios when the set of values is drawn according to a PI distribution. Our results complement recent work of Dughmi et al. [2] showing that no omega(1/k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\omega (1/k)$$\end{document}-selectable OCRS exists in the PI setting for general matroids of rank k.