Key points are not available for this paper at this time.
マッチングは多くの領域で最も基本的で広く適用可能な問題の一つです。これらの多様な実世界のアプリケーションでは、入力においてしばしば不確実性があります。これが確率的マッチングモデルの研究につながりました。ここでは、グラフの各辺には予測から得られる知られた独立した存在確率があります。アルゴリズムは辺の存在を判断するために調査を行い、存在する場合はそれらを不可逆的にマッチさせなければなりません。さらに、各頂点には隣接する辺を調査できる数を示す耐久制約がある場合があります。私たちは、この分野で研究されているいくつかの基礎的な問題に対する改善された近似保証を提供する新しい順序付き競合解決手法を提案します。一般のグラフにおける耐久制約を持つ確率的マッチングのために、0.382近似アルゴリズムを提供し、従来の最良の0.31近似を大幅に改善しました。頂点に耐久制約がない場合は、複数の系統を持つ0.432近似ランダム順序調査アルゴリズムを説明します。例えば、エッジ到着下でのプロフェットセクレタリー問題に対する改善された保証などがあります。最後に、一方の分割に単位耐久制約を持つ特別な場合の二部グラフについて、1/3の保証を提供する最近の結果を改善する0.632近似アルゴリズムを示します。資金提供：N. GrammelとA. Srinivasanは、国家科学財団コンピューティングおよび通信基盤部門賞CCF-1749864から部分的に経済的支援を受け、AmazonおよびGoogleからの研究賞も受けました.
Brubachら（火曜日）はこの質問を研究しました。