抄録/ポイント:
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
1面到着とその変異体とのオンライン二分マッチングは,Karp,Vaziani,およびVaziani(STOC1990)の精巧な仕事以来,広く研究されている。動的市場構造,例えば,乗り分けによる実生活応用によって動機づけられて,古典的片側到着モデルの2つの一般化は,非二者グラフを許すために提案して,すべての頂点がオンラインに到達することを可能にした。すなわち,一般的頂点到着とのオンラインマッチングをWangとWong(ICALP 2015)によって導入し,完全にオンラインマッチングをHuang et al.(JACM2020)によって導入した。本論文では,2つのモデルの分数バージョンを研究した。2つのモデルの4つの最先端の上限と下限の3つを改良した。完全オンラインマッチングのために,0.6-競合アルゴリズムを設計し,アルゴリズムが0.613-競合であることを証明する。一般的頂点到着とのオンラインマッチングのために,著者らは,アルゴリズムが0.584競争であることができないことを証明した。さらに,WangとWongのアルゴリズムと比較して,一般的頂点到着モデルに対するより直感的なアルゴリズムを与え,一方,0.526の同じ競合比率を達成した。【JST・京大機械翻訳】