論文の概要: Three-Objective Integral R2 Subset Selection: NP-Hardness and Submodular Approximation
- arxiv url: http://arxiv.org/abs/2606.26591v1
- Date: Thu, 25 Jun 2026 04:25:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-26 18:46:32.158103
- Title: Three-Objective Integral R2 Subset Selection: NP-Hardness and Submodular Approximation
- Title（参考訳）: 3目的積分R2サブセット選択:NP-ハードネスと部分モジュラ近似
- Abstract要約: 本稿では3つの目的において積分R2インジケータの問題点を考察する。
任意の固定基底線に対する積分 R2 の改善は単調部分モジュラー集合函数であることを示す。
また, 完全積分 R2 値を部分分割で評価するグリージーな実装も提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Selecting a fixed number of representative points from a finite Pareto-front approximation is a fundamental post-processing task in multiobjective optimization. This paper studies this problem for the integral R2 indicator in three objectives, where the indicator is defined as the integral of the lower envelope of weighted Tchebycheff scalarizations over the two-dimensional weight simplex. We provide two complementary algorithmic results. On the positive side, we show that the integral R2 improvement with respect to any fixed baseline is a monotone submodular set function. For the usual ideal-point based R2 indicator, with the ideal point fixed, this yields a direct gap-reduction guarantee: greedy selection closes at least a $(1-1/e)$-fraction of the maximum possible R2 gap between a fixed dominated anchor value and the best cardinality-$k$ value. We also give a tested greedy implementation that evaluates exact integral R2 values by subdivision, with worst-case running time $O(n^6)$. On the negative side, we prove that exact fixed-cardinality subset selection is NP-hard already in three objectives. The hardness proof uses a perspective transformation that maps Tchebycheff-shadow improvements to a weighted anchored-box union problem with density $(x_1+x_2+x_3)^{-4}$, and then adapts the three-dimensional anchored-box construction of Bringmann, Cabello, and Emmerich. Together, these results separate the tractable two-objective case from the three-objective case while identifying a principled approximation route based on submodular optimization.
- Abstract（参考訳）: 有限パレートフロント近似から一定数の代表点を選択することは、多目的最適化における基本的な後処理タスクである。
本稿では、3つの目的において積分R2インジケータのこの問題について検討する。そこでは、このインジケータを2次元の重み付きチェビシェフスカラー化の下層エンベロープの積分として定義する。
2つの補完的なアルゴリズム結果を提供する。
正の面において、任意の固定基底線に対する積分 R2 の改善は単調部分モジュラー集合函数であることを示す。
理想点が固定された通常のイデアル点ベースのR2指標に対して、これは直接ギャップ還元を保証する: グリーディ選択は、固定された支配的アンカー値と最高濃度−k$値の間の最大可能なR2ギャップの少なくとも1-1/e)$-フレクションを閉じる。
また、試行錯誤により正確な積分R2値をサブディビジョンで評価し、最悪の実行時間は$O(n^6)$である。
負側では、正確な不動部分集合選択が既に3つの目的においてNPハードであることが証明される。
硬度証明は、チェビシェフ・シャドウ改善を密度$(x_1+x_2+x_3)^{-4}$で重み付きアンカーボックス結合問題にマッピングするパースペクティブ変換を使用し、次に、リープマン、カベロ、エメリッヒの3次元アンカーボックス構成に適応する。
これらの結果と合わせて, トラクタブルな2物体の場合と3物体の場合とを分離し, 部分モジュラー最適化に基づく原理的近似経路を同定した。
関連論文リスト
- Computing the Integral R2 Indicator by Perspective Mapping and Box Decomposition [0.0]
この研究は、連続積分 R2 計算と固定軸整列箱の和集合上の積分の間の双方向の視点写像を導入する。
ボックス分解を出力するハイパーボリュームアルゴリズムは、通常のボックスボリュームを閉形式重み付きボックス積分に置き換えることで再利用することができる。
論文 参考訳（メタデータ） (2026-06-29T16:34:01Z) - Solve for the Hyperparameter, Skip the Search: Kolmogorov-Optimal Scaling Laws for Spline Regression [0.0]
クローズドな形での最適解法は、徹底的な探索が到達した精度を計算のごく一部で解くことができる。
KOREは2つのパイロット解像度に適合し、バイアスとノイズスケールのレバレッジ校正された2x2システムを解く。
論文 参考訳（メタデータ） (2026-06-22T16:41:10Z) - Distributionally Robust Multi-Objective Optimization [47.16280600850848]
分散ロバストな多目的最適化(DRMOO)を導入する。
本稿では、内部ループを用いて2変数を推定し、$$$Pareto-stationary点に達するための合計サンプル複雑性を$mathcalO(-12)$とする2ループMGDAを提案する。
さらに効率を向上させるために、一般化された平滑な偏り推定を処理し、二重サンプリングの必要性を排除した。
論文 参考訳（メタデータ） (2026-05-07T04:24:17Z) - DC-Reg: Globally Optimal Point Cloud Registration via Tight Bounding with Difference of Convex Programming [43.06401929828342]
我々は,グローバルに最適なポイント登録インタフェースを実現するための新しいフレームワークを開発した。
その結果, 極端雑音への収束が著しく速くなり, 極端雑音へのアウトリー・オブ・ザ・アートのグローバル化が可能となった。
論文 参考訳（メタデータ） (2026-03-26T13:38:45Z) - An Information-Minimal Geometry for Qubit-Efficient Optimization [0.0]
量子ビット効率の最適化を幾何学的問題として再検討する。
局所一貫性問題は、Sherali-Adams level-2 polytope $mathrmSA(2)$とちょうど一致する。
論文 参考訳（メタデータ） (2025-11-11T15:38:57Z) - Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - Decomposed Global Optimization for Robust Point Matching with Low-Dimensional Branching [41.05165517541873]
部分重なり合う点集合を整列する新しい大域的最適化手法を提案する。
本手法は非剛性変形, 位置雑音, 外れ値に優れた強靭性を示す。
2次元および3次元合成および実世界のデータを用いた実験により,本手法は最先端の手法と比較して,外れ値に対して優れた強靭性を示すことが示された。
論文 参考訳（メタデータ） (2024-05-14T13:28:57Z) - Polynomial-Time Solutions for ReLU Network Training: A Complexity
Classification via Max-Cut and Zonotopes [70.52097560486683]
我々は、ReLUネットワークの近似の難しさがマックス・カッツ問題の複雑さを反映しているだけでなく、特定の場合において、それと完全に一致することを証明した。
特に、$epsilonleqsqrt84/83-1approx 0.006$とすると、目的値に関して相対誤差$epsilon$でReLUネットワーク対象の近似グローバルデータセットを見つけることはNPハードであることが示される。
論文 参考訳（メタデータ） (2023-11-18T04:41:07Z) - Gradient-Free Methods for Deterministic and Stochastic Nonsmooth
Nonconvex Optimization [94.19177623349947]
非滑らかな非最適化問題は、機械学習とビジネス製造に現れる。
2つのコア課題は、有限収束を保証する効率的な方法の開発を妨げる。
GFMとSGFMの2相版も提案され, 改良された大規模評価結果が得られた。
論文 参考訳（メタデータ） (2022-09-12T06:53:24Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。
まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。
次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-01-19T04:24:23Z) - Canny-VO: Visual Odometry with RGB-D Cameras based on Geometric 3D-2D
Edge Alignment [85.32080531133799]
本稿では,自由形式の曲線登録に関する古典的な問題をレビューし,効率的なrgbdビジュアルオドメトリシステムcanny-voに適用する。
エッジ登録でよく用いられる距離変換の代替として、近似近接近傍場と配向近接近傍場という2つの方法が提案されている。
3D2Dエッジアライメントは、効率性と精度の両方の観点から、これらの代替製剤の恩恵を受けます。
論文 参考訳（メタデータ） (2020-12-15T11:42:17Z) - Robust 6D Object Pose Estimation by Learning RGB-D Features [59.580366107770764]
本稿では、この局所最適問題を解くために、回転回帰のための離散連続的な新しい定式化を提案する。
我々はSO(3)の回転アンカーを均一にサンプリングし、各アンカーから目標への制約付き偏差を予測し、最適な予測を選択するための不確実性スコアを出力する。
LINEMOD と YCB-Video の2つのベンチマーク実験により,提案手法が最先端の手法より優れていることが示された。
論文 参考訳（メタデータ） (2020-02-29T06:24:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。