論文の概要: Corporate Needs You to Find the Difference: Revisiting Submodular and Supermodular Ratio Optimization Problems

• arxiv url: http://arxiv.org/abs/2505.17443v1
• Date: Fri, 23 May 2025 03:55:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-26 18:08:33.801676
• Title: Corporate Needs You to Find the Difference: Revisiting Submodular and Supermodular Ratio Optimization Problems
• Title（参考訳）: コーポレートは違いを見つける必要がある: 部分モジュラーと超モジュラー比最適化の問題を再考する
• Authors: Elfarouk Harb, Yousef Yassin, Chandra Chekuri,
• Abstract要約: 平均値 $ f(S)/|S| $ を小モジュラーあるいは超モジュラーな集合関数 f: 2V から算術 $ への最小化や最大化の問題について研究する。 これは、Densest Subgraph (DSG)、Densest Supermodular Set (DSS)、Submodular Minimization (SFM)といった古典的な問題を一般化する。
• 参考スコア（独自算出の注目度）: 3.637365301757111
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of minimizing or maximizing the average value $ f(S)/|S| $ of a submodular or supermodular set function $ f: 2^V \to \mathbb{R} $ over non-empty subsets $ S \subseteq V $. This generalizes classical problems such as Densest Subgraph (DSG), Densest Supermodular Set (DSS), and Submodular Function Minimization (SFM). Motivated by recent applications, we introduce two broad formulations: Unrestricted Sparsest Submodular Set (USSS) and Unrestricted Densest Supermodular Set (UDSS), which allow for negative and non-monotone functions. We show that DSS, SFM, USSS, UDSS, and the Minimum Norm Point (MNP) problem are equivalent under strongly polynomial-time reductions, enabling algorithmic crossover. In particular, viewing these through the lens of the MNP in the base polyhedron, we connect Fujishige's theory with dense decomposition, and show that both Fujishige-Wolfe's algorithm and the heuristic \textsc{SuperGreedy++} act as universal solvers for all these problems, including sub-modular function minimization. Theoretically, we explain why \textsc{SuperGreedy++} is effective beyond DSS, including for tasks like submodular minimization and minimum $ s $-$ t $ cut. Empirically, we test several solvers, including the Fujishige-Wolfe algorithm on over 400 experiments across seven problem types and large-scale real/synthetic datasets. Surprisingly, general-purpose convex and flow-based methods outperform task-specific baselines, demonstrating that with the right framing, general optimization techniques can be both scalable and state-of-the-art for submodular and supermodular ratio problems.
• Abstract（参考訳）: 平均値 $ f(S)/|S| $ の非空部分集合 $ S \subseteq V $ 上の部分モジュラーあるいは超モジュラー集合関数 $ f: 2^V \to \mathbb{R} $ の最小化または最大化の問題を研究する。 これは、Densest Subgraph (DSG)、Densest Supermodular Set (DSS)、Submodular Function Minimization (SFM)といった古典的な問題を一般化する。 最近の応用に触発されて、負と非単調の関数を可能にするunrestricted Sparsest Submodular Set (USSS)とUnrestricted Densest Supermodular Set (UDSS)の2つの広い定式化を導入する。 DSS, SFM, USSS, UDSS, および最小ノルム点(MNP)問題は、強い多項式時間短縮の下で等価であり、アルゴリズム的クロスオーバーを可能にする。 特に、基本多面体における MNP のレンズを通してこれらを見ることで、藤重・ウォルフのアルゴリズムとヒューリスティックな \textsc{SuperGreedy++} が、部分モジュラー函数の最小化を含むこれらの問題に対する普遍的な解法として働くことを示す。 理論的には、submodular minimization や s $-$ t $ cut といったタスクを含む DSS を超えて \textsc{SuperGreedy++} が有効である理由を説明します。 実験では, 富士重ウルフアルゴリズムを7種類の問題種, 大規模実・合成データセットで400以上の実験を行った。 驚くべきことに、汎用凸法とフローベース法はタスク固有のベースラインよりも優れており、適切なフレーミングにより、準モジュラー比問題や超モジュラー比問題に対して、拡張性と最先端の両方の最適化技術が可能であることを実証している。

関連論文リスト

• Syzygy of Thoughts: Improving LLM CoT with the Minimal Free Resolution [59.39066657300045]
  CoT(Chain-of-Thought)は、問題を逐次ステップに分解することで、大きな言語モデル(LLM)の推論を促進する。 思考のシジー(Syzygy of Thoughts, SoT)は,CoTを補助的,相互関連的な推論経路を導入して拡張する新しいフレームワークである。 SoTはより深い論理的依存関係をキャプチャし、より堅牢で構造化された問題解決を可能にする。
  論文  参考訳（メタデータ） (2025-04-13T13:35:41Z)
• Dynamic Non-monotone Submodular Maximization [11.354502646593607]
  濃度制約$k$で非単調部分モジュラ函数を最大化することから、同じ制約の下で単調部分モジュラ函数を最大化することへの還元を示す。 我々のアルゴリズムは、ソリューションの$(epsilon)$-approximateを維持し、期待される$O(epsilon-3k3log3(n)log(k)$ query per updateを使用する。
  論文  参考訳（メタデータ） (2023-11-07T03:20:02Z)
• Non-monotone Sequential Submodular Maximization [13.619980548779687]
  我々は、$k$の重み付けが最大になるように、基底セット$V$から$k$の項目群を選択してランク付けすることを目指している。 本研究の結果は,レコメンデーションシステムや最適化など,様々な分野に影響を及ぼす。
  論文  参考訳（メタデータ） (2023-08-16T19:32:29Z)
• Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback [98.29086113546045]
  本稿では,非拘束型マルチアームバンディットのフルバンドフィードバックとサブモジュール性に対する報奨問題について検討する。 RGLは、サブモジュールおよび非サブモジュール設定において、他のフルバンド変種よりも経験的に優れていることを示す。
  論文  参考訳（メタデータ） (2023-02-02T18:52:14Z)
• Submodular + Concave [53.208470310734825]
  第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。 本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。 このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
  論文  参考訳（メタデータ） (2021-06-09T01:59:55Z)
• The Power of Subsampling in Submodular Maximization [51.629656762796564]
  このアプローチは,既存の手法よりもはるかに単純であるにもかかわらず,最適/最先端の結果をもたらすことを示す。 我々は,映像要約,位置情報要約,映画推薦タスクにおけるアルゴリズムの有効性を実証的に示す。
  論文  参考訳（メタデータ） (2021-04-06T20:25:57Z)
• Adaptive Sampling for Fast Constrained Maximization of Submodular Function [8.619758302080891]
  非モノトーンサブモジュラに対する多対数適応性を有するアルゴリズムを一般側制約下で開発する。 本アルゴリズムは,$p$-system 側制約下での非単調部分モジュラ関数の最大化に適している。
  論文  参考訳（メタデータ） (2021-02-12T12:38:03Z)
• Regularized Submodular Maximization at Scale [45.914693923126826]
  亜モジュラリティは本質的に多様性、カバレッジ、代表性の概念に関係している。 正規化部分モジュラ函数 $f = g ell$ を行列式部分モジュラ関数 $g$ とモジュラ関数 $ell$ の差分として最大化する手法を提案する。
  論文  参考訳（メタデータ） (2020-02-10T02:37:18Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。