文献

J-GLOBAL ID：202202255563000885   整理番号：22A0902416

マッチングとマトロイド交差問題における辞書的最大解による近似【JST・京大機械翻訳】

Approximation by lexicographically maximal solutions in matching and matroid intersection problems

著者 (4件)： Berczi Kristof (MTA-ELTE Momentum Matroid Optimization Research Group and MTA-ELTE Egervary Research Group, Department of Operations Research, Eotvos Lorand University, Budapest, Hungary) ,  Kiraly Tamas (MTA-ELTE Momentum Matroid Optimization Research Group and MTA-ELTE Egervary Research Group, Department of Operations Research, Eotvos Lorand University, Budapest, Hungary) ,  Yamaguchi Yutaro (Department of Information and Physical Sciences, Graduate School of Information Science and Technology, Osaka University, Osaka, Japan) ,  Yokoi Yu (Principles of Informatics Research Division, National Institute of Informatics, Tokyo, Japan)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 910  ページ： 48-53  発行年： 2022年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 短報  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 著者らは,良好な辞書的最大解が加重マッチングとマトロイド交差問題においてどのように良いかを研究した。解は,可能な限り多くの最も重い要素をとるならば,辞書的に最大であり,これに従えば,できるだけ多くの第2の重い要素として取り込まれる。明確な重み値が十分に分散されるならば,2つの異なる重量値の最小比率は少なくとも地上集合サイズであり,次に,辞書的最大性と通常の加重最適性は等価である。保持に対するこの等価比の閾値は,厳密に2であることを示した。さらに,もし比が2以下のならば,α,次に,辞書的に最大解が(α/2)近似を達成し,この限界が強まることを証明した。Copyright 2022 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *近似法 ,  交差 ,  *マトロイド ,  *マッチング ,  *辞書

著者キーワード (4件)： マッチング ,  マトロイド交差 ,  辞書的最大性 ,  近似比

分類 (2件)： 図形・画像処理一般  (JE04010I) ,  グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (6件)： マッチング ,  マトロイド ,  交差 ,  辞書 ,  解 ,  近似