Matroid マッチングの仕組みパート 3(機械学習 2024) | Monodeep Mukherjee 著 | 2024年3月

1. 需要マッチングのさらなる近似: マトロイド制約とマイナー閉グラフ(arXiv)

著者 ： サラ・アフマディアン、 ザカリー・フリッグスタッド

要約 : 私たちは、b-Matching 問題と Knapsack 問題を共通に一般化した一般化需要照合問題の研究を追求します。 ここでは、頂点の容量、エッジの利益、エッジ上の非対称の需要を示すグラフが表示されます。 目標は、選択したエッジの要求が頂点の容量を侵害しないように、最大の利益をもたらすエッジのサブセットを見つけることです。 この問題は APX 困難であり、定数因数近似が知られています。 私たちの結果は 2 つのカテゴリに分類されます。 まず、反復緩和とさまざまなフィルタリング戦略を使用して、追加のマトロイド構造 M が与えられ、さらに M で独立した集合 F⊆E のみが許可される場合、自然な LP 緩和には 0.5 の整数ギャップがあることを効率的な丸めアルゴリズムで示します。ほとんどは 253 ≈ 8.333 です。 これはさまざまな特殊なケースで改善できます。たとえば、以前に研究した結合配置問題の 15 近似を改善します。 [Korupolu et al. 2014] 7 近似を与えることによって。 同様の手法を使用して、頂点容量を満たす M の最小コスト ベースを計算する問題が (1,3)-bicriteria 近似を許容することを示します。 これは、M が指定されたグラフ上のグラフィック マトロイドであるという特殊なケースにおける以前の (1,4) 近似よりも改善されています。 [Fukanaga and Nagamochi, 2009]。 第 2 に、需要マッチングが固定マイナーを除外したグラフでの多項式時間近似スキームを許容することを示します。 すべての要求が多項式で制限された整数である場合、制限されたツリー幅グラフで動的プログラミングを使用すると、これはある程度簡単になります。 私たちの主な技術的貢献は、スパース化補題により、より複雑な動的プログラミング アルゴリズムで使用される要求をスケーリングできるようにし、その後、スケーリングされた要求のソリューションを実行可能なソリューションにフィルタリングするためにランダム化された丸めが行われることです。

2.マッチングおよびマトロイド交差問題における辞書編集上の最大解による近似 (arXiv)

著者 ： クリストフ・ベルツィ、 タマス・キラーリ、 Yutaro Yamaguchi、 Yu Yokoi

要約 : 重み付けマッチング問題とマトロイド交差問題において、辞書編集上の最大解がどの程度優れているかを研究します。 可能な限り多くの最も重い要素を使用する場合、解は辞書編集的に最大であり、これに従って、可能な限り多くの 2 番目に重い要素が必要になります。 個別の重み値が十分に分散している場合、たとえば 2 つの個別の重み値の最小比が少なくともグランドセットサイズである場合、辞書編集上の最大値と通常の重み付け最適性は同等になります。 この等価性が維持される比率の閾値は正確に 2 であることを示します。さらに、比率が 2 未満、たとえば α の場合、辞書編集上の最大解は (α/2) 近似を達成し、この限界が得られることを証明します。きついです。