論文の概要: Matroid Algorithms Under Size-Sensitive Independence Oracles

• arxiv url: http://arxiv.org/abs/2605.00201v1
• Date: Thu, 30 Apr 2026 20:26:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-04 17:43:28.743161
• Title: Matroid Algorithms Under Size-Sensitive Independence Oracles
• Title（参考訳）: 小型感性独立オラクルにおけるマトロイドアルゴリズム
• Authors: Kiarash Banihashem, MohammadTaghi Hajiaghayi, Mahdi JafariRaviz, Danny Mittal,
• Abstract要約: Matroidアルゴリズムは、各独立性クエリは、クエリセットのサイズに関わらず、一定時間で答えられると仮定する。 特に、グラフィック・マトロイドのような自然で広く研究されているクラスでは、単一の独立性クエリでさえ、集合のサイズで線形な作業を必要とすることがある。 クエリのコストを$|Q|$でスケールする,サイズに敏感なコストモデルを導入する。
• 参考スコア（独自算出の注目度）: 19.61677355524952
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The standard oracle model for matroid algorithms assumes that each independence query can be answered in constant time, regardless of the size of the queried set. While this abstraction has underpinned much of the theoretical progress in matroid optimization, it masks the true computational effort required by these algorithms. In particular, for natural and widely studied classes such as graphic matroids, even a single independence query can require work linear in the size of the set, making the constant-time assumption implausible. We address this gap by introducing a size-sensitive cost model where the cost of a query $Q$ scales with $|Q|$. Nearly linear-time oracle implementations exist for broad families of matroids, and this refined abstraction therefore captures the true cost of query evaluation while allowing for a more faithful comparison between general matroids and their natural special cases. Within this framework we study three fundamental algorithmic tasks: finding a basis of a matroid, approximating its rank, and approximating its partition size. We establish tight results, proving nearly matching upper and lower bounds that show the optimal query cost is (up to logarithmic factors) quadratic in the size of the matroid. On the algorithmic side, our upper bounds are realized by explicit procedures that construct the desired solution. On the complexity side, our lower bounds are unconditional and already hold even for weaker distinguishing formulations of the problems. Finally, for matroids with maximum circuit size at most $c$, we show that the quadratic barrier can be broken, providing an algorithm that calculates the maximum-weight basis with expected query cost $\mathcal{O}(n^{2-1/c} \log n)$.
• Abstract（参考訳）: マトロイドアルゴリズムの標準的なオラクルモデルは、クエリセットのサイズに関係なく、それぞれの独立性クエリを一定時間で答えられると仮定する。 この抽象化は、マトロイド最適化の理論的進歩の多くを支えているが、これらのアルゴリズムが必要とする真の計算努力を隠蔽している。 特に、グラフィック・マトロイドのような自然で広く研究されているクラスでは、単一の独立性クエリでさえ、集合のサイズで線形な作業を必要とするため、定数時間仮定は不可解である。 クエリのコストが$|Q|$でスケールするサイズ感受性コストモデルを導入することで、このギャップに対処する。 概して線形時間オラクルの実装は、マトロイドの広いファミリーに存在し、この洗練された抽象化は、一般的なマトロイドとそれらの自然な特殊ケースとのより忠実な比較を可能にしながら、クエリ評価の真のコストを捉えている。 このフレームワーク内では、マトロイドの基底を見つけ、そのランクを近似し、パーティションサイズを近似する3つの基本的なアルゴリズムタスクについて研究する。 最適クエリコストが(対数因子まで)マトロイドのサイズを2次的に表すような、ほぼ一致する上と下の境界を証明し、厳密な結果を確立する。 アルゴリズム側では、我々の上限は所望の解を構成する明示的な手続きによって実現される。 複雑性面では、下界は無条件であり、問題の定式化がより弱いとしても既に保持されている。 最後に、最大回路サイズが$c$のマトロイドに対して、2次障壁を破ることを示し、期待されるクエリコスト$\mathcal{O}(n^{2-1/c} \log n)$で最大ウェイト基底を計算するアルゴリズムを提供する。

関連論文リスト

• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Discretely Beyond $1/e$: Guided Combinatorial Algorithms for Submodular Maximization [13.86054078646307]
  制約のある、必ずしも単調な部分モジュラーでなくても、比が1/e$より大きい全ての既知の近似アルゴリズムは連続的な考えを必要とする。 アルゴリズムでは, 単純なランダム化グレディアルゴリズムを用いて, サイズとマトロイドの制約の双方について最もよく知られた近似比を求める。
  論文  参考訳（メタデータ） (2024-05-08T16:39:59Z)
• Accelerating Matroid Optimization through Fast Imprecise Oracles [40.94053997358159]
  汚いオラクルの品質について,クリーンなクエリをほとんど使用しない実用的なアルゴリズムを解析する。 特に、我々のアルゴリズムは、多くの点で、最も有益であることを示す。 我々は、他のマトロイドオラクルタイプ、非自由な汚いオークル、その他のマトロイド問題への拡張を概説する。
  論文  参考訳（メタデータ） (2024-02-05T07:14:18Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• Quick Streaming Algorithms for Maximization of Monotone Submodular Functions in Linear Time [16.346069386394703]
  単調な部分モジュラー(submodular)の問題を、濃度制約に従えば$n$の基底集合上で考える。 線形時間複雑性を持つ最初の決定論的アルゴリズムを導入し,これらのアルゴリズムはストリーミングアルゴリズムである。 我々のシングルパスアルゴリズムは任意の$c ge 1$に対して$lceil n / c rceil + c$ oracle クエリの定数比を得る。
  論文  参考訳（メタデータ） (2020-09-10T16:35:54Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)

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

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