抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
確率的マッチング問題を考察した。エッジ加重一般(すなわち,必ずしも二部ではない)グラフG(V,E)を入力に与え,そこでは,Eの各エッジを確率pで独立に実現した。実現は最初に未知であるが,それらが実現されるかどうかを決定するためにエッジを問うことができる。目標は,すべての実現エッジの中で最大マッチングに十分近い実現マッチングを見つけるため,少数のエッジだけをクエリすることである。確率的マッチング問題は,腎臓交換,マッチメイキングサービス,オンライン労働市場,広告における多数の実世界応用のため,Chen et al.[ICALP’09の初期論文の後,過去10年間かなりの注目を受けた。著者らの研究に最も関連するのは,確率マッチングの同じモデルを考慮するBlumら[EC’15,Assadiら[EC’16,EC’17]およびMaeharaおよびYamaguchi Tukey(SODA’18)の最近の論文である。著者らの主な結果は,任意の任意に小さいΔΨ0に対する適応アルゴリズムであり,頂点当たりのO(1)エッジのみをクエリすることにより,期待値における(1-ε)近似を見つける。さらに,提案アプローチは,頂点あたりO(1)エッジを用いる(1/2-ε)近似非適応アルゴリズムを導くことを示した。著者等の研究の前に,非自明な近似は,一定/頂点予算を用いた加重グラフに対して知られていなかった。MaeharaとYamaguchiの最先端の適応(resp.非適応)アルゴリズムは,(1-ε)近似(resp)を達成した。(1/2-ε)近似は,wが最大整数エッジ重みを示す頂点当りO(wlogn)エッジを問い合わせることにより,近似する。この結果は,この限界に対する実質的な改善であり,入力グラフの構造がどのように,1頂点あたり一定数のエッジだけを問い合わせることにより最適解に任意に近づけることができるという魅力的なメッセージを持つ。筆者らの結果を得るために,著者らは,独立した興味の可能性がある加重マッチングへの増加経路の一般化の新しい特性を導入した。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】
