論文の概要: Partial Optimality in the Preordering Problem

• arxiv url: http://arxiv.org/abs/2602.17346v1
• Date: Thu, 19 Feb 2026 13:29:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-20 15:21:29.039774
• Title: Partial Optimality in the Preordering Problem
• Title（参考訳）: プレオーダー問題における部分最適性
• Authors: David Stein, Jannik Irmai, Bjoern Andres,
• Abstract要約: 事前順序付け(Preordering)は、バイオインフォマティクスとソーシャルネットワーク分析の応用によるクラスタリングと部分順序付けの一般化である。 我々はこれらの条件を決定するための新しい部分最適条件と効率的なアルゴリズムを提案する。 実データと合成データを用いた実験では、これらの新しい条件は特に、$a notlesssim b$を最適な事前順序で効率的に決定するペアの$ab$の分数を増加させる。
• 参考スコア（独自算出の注目度）: 10.743817805407785
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Preordering is a generalization of clustering and partial ordering with applications in bioinformatics and social network analysis. Given a finite set $V$ and a value $c_{ab} \in \mathbb{R}$ for every ordered pair $ab$ of elements of $V$, the preordering problem asks for a preorder $\lesssim$ on $V$ that maximizes the sum of the values of those pairs $ab$ for which $a \lesssim b$. Building on the state of the art in solving this NP-hard problem partially, we contribute new partial optimality conditions and efficient algorithms for deciding these conditions. In experiments with real and synthetic data, these new conditions increase, in particular, the fraction of pairs $ab$ for which it is decided efficiently that $a \not\lesssim b$ in an optimal preorder.
• Abstract（参考訳）: 事前順序付け(Preordering)は、バイオインフォマティクスとソーシャルネットワーク分析の応用によるクラスタリングと部分順序付けの一般化である。 有限集合 $V$ と任意の順序対 $ab$ に対して $c_{ab} \in \mathbb{R}$ が与えられたとき、プレオーダー問題は、それらのペアの値の和を最大化する $V$ のプレオーダー $\lesssim$ を求める。 このNP-ハード問題を部分的に解くための最先端技術に基づいて、我々はこれらの条件を決定するための新しい部分最適条件と効率的なアルゴリズムを貢献する。 実データと合成データを用いた実験では、これらの新しい条件は特に、ペアの$ab$の分数を増やし、この分数は、最適な事前順序で$a \not\lesssim b$と効率的に決定される。

関連論文リスト

• Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity [0.0]
  我々は最も高速な決定論的アルゴリズムの近似係数を6+epsilon$から5+epsilon$に改善する。 本手法は, しきい値のグリーディ・サブルーチンと, 候補解としての2つの解集合の構築という, 2つの成分の性能を最適化することに基づいている。
  論文  参考訳（メタデータ） (2024-05-20T02:24:58Z)
• The Computational Complexity of Finding Stationary Points in Non-Convex Optimization [53.86485757442486]
  近似定常点、すなわち勾配がほぼゼロの点を見つけることは、非順序だが滑らかな目的函数の計算問題である。 制約付き最適化における近似KKT点の発見は、制約なし最適化における近似定常点の発見に対して再現可能であるが、逆は不可能であることを示す。
  論文  参考訳（メタデータ） (2023-10-13T14:52:46Z)
• On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation [13.813242559935732]
  両レベル最適化問題の1次解法について述べる。 特に,ペナルティ関数と超目的物との間に強い関連性を示す。 その結果,O(epsilon-3)$とO(epsilon-5)$が改良された。
  論文  参考訳（メタデータ） (2023-09-04T18:25:43Z)
• Dynamic Algorithms for Matroid Submodular Maximization [11.354502646593607]
  マトロイドおよび濃度制約の下でのサブモジュラー複雑性は、機械学習、オークション理論、最適化における幅広い応用の問題である。 本稿では、これらの問題を動的に考慮し、モノトン部分モジュラ関数 $f: 2V rightarrow mathbbR+$ にアクセスでき、基底となる基底集合 $V$ の元の挿入と削除のシーケンス $calmathS$ が与えられる。 マトロイド制約下でのサブモジュラー問題に対する最初の完全動的アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2023-06-01T17:54:15Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。 特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
  論文  参考訳（メタデータ） (2023-01-10T20:43:29Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。 我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。 我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
  論文  参考訳（メタデータ） (2022-09-30T04:15:44Z)
• The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization [88.91190483500932]
  本研究では,滑らかな凸最小化問題の解法として最適高次アルゴリズムを求めるための基本的オープンな問題について検討する。 この理由は、これらのアルゴリズムが複雑なバイナリプロシージャを実行する必要があるため、最適でも実用でもないからである。 我々は、最初のアルゴリズムに$mathcalOleft(epsilon-2/(p+1)right)$pthのオーダーオーラクル複雑性を与えることで、この根本的な問題を解決する。
  論文  参考訳（メタデータ） (2022-05-19T16:04:40Z)
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
  私たちは発見するアルゴリズムを見つけます。 epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using $(epsilon,gamma)$surimateランダムランダムポイント。 ここでの私たちの下限は、ノイズのないケースでも新規です。
  論文  参考訳（メタデータ） (2020-06-24T04:41:43Z)

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

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