Scholarlink

<p>We consider the classical online bipartite matching problem in the probe-commit model. In this problem, when an online vertex arrives, its edges must be probed to determine if they exist, based on known edge probabilities. A probing algorithm must respect commitment, meaning that if a probed edge exists, it must be used in the matching. Additionally, each online vertex has a patience constraint which limits the number of probes that can be made to its adjacent edges. We introduce a new configuration linear program and use it to establish the following competitive ratios which depend on the model used to generate the instance graph, and the arrival order of its online vertices:<UnorderedList Mark="Bullet"> <ItemContent> <p>In the worst-case instance model, an optimal 1/<i>e</i> ratio when the vertices arrive in uniformly at random (u.a.r.) order.</p> </ItemContent> <ItemContent> <p>In the known independently distributed (i.d.) instance model, an optimal 1/2 ratio when the vertices arrive in adversarial order, and a <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(1-1/e\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1</mn> <mo>-</mo> <mn>1</mn> <mo stretchy="false">/</mo> <mi>e</mi> </mrow> </math></EquationSource> </InlineEquation> ratio when the vertices arrive in u.a.r. order.</p> </ItemContent> </UnorderedList> The latter two results improve upon the previous best competitive ratio of 0.46 due to Brubach et al. (Algorithmica 2020). Our <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(1-1/e\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1</mn> <mo>-</mo> <mn>1</mn> <mo stretchy="false">/</mo> <mi>e</mi> </mrow> </math></EquationSource> </InlineEquation>-competitive algorithm matches the best known result for the prophet secretary matching problem due to Ehsani et al. (SODA 2018). Our algorithm is efficient and implies a <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(1-1/e\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1</mn> <mo>-</mo> <mn>1</mn> <mo stretchy="false">/</mo> <mi>e</mi> </mrow> </math></EquationSource> </InlineEquation> approximation ratio for the special case when the graph is known. This is the offline stochastic matching problem, and we improve upon the 0.42 approximation ratio for one-sided patience due to Pollner et al. (EC 2022), while also generalizing the <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(1-1/e\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1</mn> <mo>-</mo> <mn>1</mn> <mo stretchy="false">/</mo> <mi>e</mi> </mrow> </math></EquationSource> </InlineEquation> approximation ratio for unbounded patience due to Gamlath et al. (SODA 2019).</p>

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

Online bipartite matching in the probe-commit model

  • 期刊论文

  • 发表日期：

    2025年1月3日

查看全文
  • Allan Borodin,
  • Calum MacRury

摘要

We consider the classical online bipartite matching problem in the probe-commit model. In this problem, when an online vertex arrives, its edges must be probed to determine if they exist, based on known edge probabilities. A probing algorithm must respect commitment, meaning that if a probed edge exists, it must be used in the matching. Additionally, each online vertex has a patience constraint which limits the number of probes that can be made to its adjacent edges. We introduce a new configuration linear program and use it to establish the following competitive ratios which depend on the model used to generate the instance graph, and the arrival order of its online vertices:

In the worst-case instance model, an optimal 1/e ratio when the vertices arrive in uniformly at random (u.a.r.) order.

In the known independently distributed (i.d.) instance model, an optimal 1/2 ratio when the vertices arrive in adversarial order, and a \(1-1/e\) 1 - 1 / e ratio when the vertices arrive in u.a.r. order.

 The latter two results improve upon the previous best competitive ratio of 0.46 due to Brubach et al. (Algorithmica 2020). Our \(1-1/e\) 1 - 1 / e -competitive algorithm matches the best known result for the prophet secretary matching problem due to Ehsani et al. (SODA 2018). Our algorithm is efficient and implies a \(1-1/e\) 1 - 1 / e approximation ratio for the special case when the graph is known. This is the offline stochastic matching problem, and we improve upon the 0.42 approximation ratio for one-sided patience due to Pollner et al. (EC 2022), while also generalizing the \(1-1/e\) 1 - 1 / e approximation ratio for unbounded patience due to Gamlath et al. (SODA 2019).