分数オンラインマッチング問題のための改良型限界【JST・京大機械翻訳】

Tang Zhihao Gavin; Zhang Yuhao

プレプリント

J-GLOBAL ID：202202206151249258 整理番号：22P0285560

分数オンラインマッチング問題のための改良型限界【JST・京大機械翻訳】

Improved Bounds for Fractional Online Matching Problems

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (2件)： ,
資料名：
発行年： 2022年02月07日プレプリントサーバーでの情報更新日： 2022年02月08日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

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・京大機械翻訳】

, , , , , , , , ,
, , , 【Automatic Indexing@JST】

グラフ理論基礎

, , , ,

前のページに戻る