Scholarlink

<p>We study online contention resolution schemes (OCRSes) and prophet inequalities for non-product distributions. Specifically, when the active set is sampled according to a <i>pairwise-independent</i> (PI) distribution, we show a <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\((1-o_k(1))\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo>-</mo> <msub> <mi>o</mi> <mi>k</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-selectable OCRS for uniform matroids of rank <i>k</i>, and <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\Omega (1)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Ω</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-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. [<CitationRef CitationID="CR2">2</CitationRef>] showing that no <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\omega (1/k)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ω</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">/</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-selectable OCRS exists in the PI setting for general matroids of rank <i>k</i>.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Pairwise-independent contention resolution

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年7月10日

查看全文
  • Anupam Gupta,
  • Jinqiao Hu,
  • Gregory Kehne,
  • Roie Levin

摘要

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-o_k(1))\) ( 1 - o k ( 1 ) ) -selectable OCRS for uniform matroids of rank k, and \(\Omega (1)\) Ω ( 1 ) -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)\) ω ( 1 / k ) -selectable OCRS exists in the PI setting for general matroids of rank k.