文献

J-GLOBAL ID：202202250708893712   整理番号：22A0917481

ほぼ線形時間における決定論的減衰SSSPと近似最小コストフロー【JST・京大機械翻訳】

Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time

著者 (3件)： Bernstein Aaron (Rutgers University New Brunswick,USA) ,  Gutenberg Maximilian Probst (ETH Zurich,Switzerland) ,  Saranurak Thatchaphol (University of Michigan,USA)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2022  号： FOCS  ページ： 1000-1008  発行年： 2022年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 減衰単一ソース最短経路問題において,目標はエッジ欠損を受けるmエッジグラフにおいて固定ソースから各頂点vまでの距離を維持することである。本論文では,(1+E)-近似距離推定を維持し,m1+o(1)全更新時間で動作する,近最適決定論的データ構造を示すことにより,この問題に関する長いラインを結論づける。特に,筆者らの結果は,Henzingerら[FOCS’14]による以前のブレークスルー結果によって要求される ob雑な敵対的仮定を除去し,これは,容量とコストがエッジと頂点で取られる,非有向グラフにおける最初のほぼ線形時間アルゴリズムである(1-E)に対する最初のほぼ線形の時間アルゴリズムが,非有向グラフにおいて,約1次的時間アルゴリズムとなることを示した;という結果を得るものである。”1-E”に対する最初のほぼ線形の時間アルゴリズムは,エッジと頂点を上回ることができる。”1-E”に対する最初のほぼ線形の時間アルゴリズムは,非有向グラフにおける最初のほぼ線形の時間アルゴリズムである。以前に,頂点容量を有する最大フローのためのアルゴリズム,または,任意の容量を有する最小コストフローは,超線形時間を必要とした。結果は,基本的に,無向グラフにおける近似流に対する描像を完成する。最初の結果の鍵となる技術は,膨張機のような低直径グラフを扱うことができる新しいフレームワークである。これにより,エキスパンダ分解の短所を迂回しながら,エキスパンダ特性を利用することができ,これは,ほとんど全ての以前のエキスパンダベースアルゴリズムが処理する必要がある。第2の結果では,ランダム化を用いて乗法的重み更新フレームワークから悪名な流れ分解障壁を破る。Copyright 2022 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  最短路問題 ,  データ構造 ,  有向グラフ ,  *近似法 ,  乗算 ,  無向グラフ ,  線形性
準シソーラス用語： 線形時間アルゴリズム ,  膨張機 ,  *決定論 ,  エキスパンダ ,  距離推定 , 【Automatic Indexing@JST】

分類 (1件)： 図形・画像処理一般  (JE04010I)

タイトルに関連する用語 (4件)： 線形 ,  減衰 ,  近似 ,  フロー