論文の概要: Preordering: A hybrid of correlation clustering and partial ordering
- arxiv url: http://arxiv.org/abs/2502.14536v1
- Date: Thu, 20 Feb 2025 13:12:03 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-21 17:44:18.285842
- Title: Preordering: A hybrid of correlation clustering and partial ordering
- Title（参考訳）: 事前順序付け:相関クラスタリングと部分順序付けのハイブリッド
- Authors: Jannik Irmai, Maximilian Moeller, Bjoern Andres,
- Abstract要約: プレオーダーは、$-1,0,1$の値であってもNPハードのままであることを示す。
線形時間 4$-approximation アルゴリズムと局所探索手法を導入する。
- 参考スコア（独自算出の注目度）: 2.7651063843287718
- License:
- Abstract: We discuss the preordering problem, a joint relaxation of the correlation clustering problem and the partial ordering problem. We show that preordering remains NP-hard even for values in $\{-1,0,1\}$. We introduce a linear-time $4$-approximation algorithm and a local search technique. For an integer linear program formulation, we establish a class of non-canonical facets of the associated preorder polytope. By solving a non-canonical linear program relaxation, we obtain non-trivial upper bounds on the objective value. We provide implementations of the algorithms we define, apply these to published social networks and compare the output and efficiency qualitatively and quantitatively.
- Abstract（参考訳）: 本稿では,事前順序付け問題,相関クラスタリング問題の連立緩和,部分順序付け問題について議論する。
プレオーダーは$\{-1,0,1\}$の値であってもNPハードのままであることを示す。
線形時間 4$-approximation アルゴリズムと局所探索手法を導入する。
整数線型プログラムの定式化には、関連するプレオーダーポリトープの非標準面のクラスを確立する。
非標準線形プログラム緩和を解くことにより、目的値の非自明な上限を求める。
我々は、定義したアルゴリズムの実装を提供し、これらを公開ソーシャルネットワークに適用し、その出力と効率を質的かつ定量的に比較する。
関連論文リスト
- Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳（メタデータ） (2023-10-20T12:45:12Z) - First-order Methods for Affinely Constrained Composite Non-convex
Non-smooth Problems: Lower Complexity Bound and Near-optimal Methods [23.948126336842634]
合成非滑らかな最適化問題の解法として, 1次FOMのより低い複雑性境界を確立するための最初の試みを行う。
本手法と提案したIGG法は,ほぼ改善可能であることがわかった。
論文 参考訳（メタデータ） (2023-07-14T19:59:18Z) - Strictly Low Rank Constraint Optimization -- An Asymptotically
$\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。
我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
論文 参考訳（メタデータ） (2023-07-04T16:55:41Z) - Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
制約付き非線形最適化問題のオンライン統計的推測を考察する。
これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
論文 参考訳（メタデータ） (2022-05-27T00:34:03Z) - Nearly Optimal Linear Convergence of Stochastic Primal-Dual Methods for
Linear Programming [5.126924253766052]
提案手法は,高い確率で鋭いインスタンスを解くための線形収束率を示す。
また、制約のない双線型問題に対する効率的な座標ベースのオラクルを提案する。
論文 参考訳（メタデータ） (2021-11-10T04:56:38Z) - Adversarial Examples for $k$-Nearest Neighbor Classifiers Based on
Higher-Order Voronoi Diagrams [69.4411417775822]
逆例は機械学習モデルにおいて広く研究されている現象である。
そこで本研究では,$k$-nearest 近傍分類の逆ロバスト性を評価するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-11-19T08:49:10Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳（メタデータ） (2020-10-23T09:12:47Z) - Zeroth-Order Algorithms for Smooth Saddle-Point Problems [117.44028458220427]
ゼロオーダーのオラクルを用いてサドルポイント問題を解くアルゴリズムをいくつか提案する。
解析により、この項の収束率は、一階法よりも$log n$因子の方が悪いことが示されている。
また、混合構成を考慮し、その部分に対してゼロ階のオラクルを使用する1/2階法を開発する。
論文 参考訳（メタデータ） (2020-09-21T14:26:48Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z) - The {0,1}-knapsack problem with qualitative levels [2.0943517417159763]
古典的なknapsack問題の変種は、各項目が整数の重みと定性的レベルと関連付けられていると考えられる。
この関係が事前注文を定義することを示す。
本研究では,非支配的な階数濃度ベクトルの集合全体を計算するための動的プログラミングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-02-12T09:00:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。